Am I using policy based ordered_set wrong? Please help

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Question link : https://www.codechef.com/problems/AVGMED Question summary : Find number of subarrays of length K, such that average >= median and also the median and average must both be prime or non prime.

Solution link using ordered_set : https://www.codechef.com/viewsolution/39036972 Am I doing something wrong with how to use ordered_set? Or my solution is wrong itself? Please help.

Code

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define FI ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PREC cout << setprecision(10) << fixed;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T> struct cmp {
	bool operator() (T x, T y) {
		return x.first < y.first;
	}
};
template <class T> using ordered_set = tree<T, null_type, cmp<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long

const int MOD = 1e9 + 7;
const int INF = 1e9 + 9;
const int MX = 1e5 + 5;

bool isPrime[MX];
void sieve() {
	memset(isPrime, true, sizeof isPrime);
	isPrime[0] = isPrime[1] = false;
	for(int i=2;i*i<MX;i++) {
		if(isPrime[i] == false) continue;
		for(int j=i*i;j<MX;j+=i) {
			isPrime[j] = false;		
		}
	} 
}

int n, k;
int inp[MX];

#undef int 
int main() {
	#define int long long
	FI;
	sieve();
	int tt;
	cin >> tt;
	while(tt--) {
		cin >> n >> k;
		for(int i=0;i<n;i++) {
			cin >> inp[i];
		}

		ordered_set<pair<int,int> > st;
		int ans = 0;

		int sum = 0;
		for(int i=0;i<k;i++) {
			st.insert({inp[i],i});
			sum += inp[i];
		}
		int avg = sum/k;
		auto it = st.find_by_order((k-1) /2);
		assert(it != st.end());
		int med = it->first;

		assert(avg >= 0 && med >= 0);
		if(isPrime[avg] == isPrime[med] && avg >= med) ans++;

		for(int i=k;i<n;i++) {
			sum += inp[i] - inp[i-k];
			st.erase({inp[i-k], i-k});
			st.insert({inp[i], i});

			avg = sum/k;
			it = st.find_by_order((k-1) /2);
			assert(it != st.end());
			med = it->first;

			assert(avg >= 0 && med >= 0);
			if(isPrime[avg] == isPrime[med] && avg >= med) ans++;
		}
		cout << ans << endl;
	}
	
	return 0;
}

Another solution : https://www.codechef.com/viewsolution/38989875 Similar solution which got accepted. I am not to able to see what I did wrong (I am blind or what?). Can someone kindly help?

Комментарии (6)

Написать комментарий?

yesnomaybe

4 года назад, # |

Update : On changing the custom comparator function from cmp to less, the solution passed.

Custom comparator function :

template <class T> struct cmp {
	bool operator() (T x, T y) {
		return x.first < y.first;
	}
};

I am trying to create an ordered multiset, and for that using pair. I want this set to be ordered on first value. But I don't see what's wrong with my comparator function though which led to wrong answer?

Is it because there could be multiple entries with same first value but different second value, and due to that the ordered_set is not able to handle "find_by_order" correctly. But I don't see how that should be the case? As I care about order imposed only by first key of the pair.

Can someone please explain what I am missing here? And how to use ordered_set over pair<int,int> i.e ordered_multiset?

→ Ответить

ishuu7

I think you've written wrong comparator for the ordered_set. I changed it to this and It worked.

You can check AC code from here.

4 года назад, # ^ |

Yeah, I understand that something is wrong with my comparator function. But can you explain why the above didn't work?

the_hyp0cr1t3

Try

template <class T> struct cmp {
	bool operator() (T x, T y) {
		return x.first == y.first? x.second < y.second : x.first < y.first;
	}
};

← Rev. 2 →

Yeah I see that it will work, but can you explain why we need to explicitly write condition for second value in pair? As in I only want set to be sorted as per first value, and in my comparator function if first values are equal then it will return false. As I don't care about the order of entries that have same first value.

Your comparator must ensure strict weak ordering. See link. This is not limited to pbds ordered set. You can replicate similar 'bugs' with STL set.

Блог пользователя yesnomaybe