Submission #982437

#	Time	Username	Problem	Language	Result	Execution time	Memory
982437		yhkhoo	Minerals (JOI19_minerals)	C++17	85 / 100	38 ms	3976 KiB

minerals

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

typedef pair<int, int> pii;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

vector<bool> mmm;
vector<int> ran;
inline int query(int i){
	mmm[i] = !mmm[i];
	i = ran[i];
	return Query(i);
}

void Solve(int N) {
	ran.reserve(2*N+1);
	for(int i=1; i<=2*N; i++){
		ran[i] = i;
	}
	random_device rd;
    mt19937 g(rd());
	shuffle(ran.begin(), ran.end(), g);
	mmm.resize(2*N+1);
	vector<int> x, y, hint(N, N-1);
	x.reserve(N);
	y.reserve(N);
	int pre = 0;
	for(int i=1; i<=2*N; i++){
		int cur = query(i);
		if(x.size() == N){
			y.pb(i);
			continue;
		}
		if(cur == pre){
			y.pb(i);
			//cerr << " y" << i;
			hint[y.size()-1] = x.size()-1;
		}
		else{
			x.pb(i);
			//cerr << " x" << i;
		}
		pre = cur;
	}
	//cerr << '\n';
	map<pii, vector<int>> sex;
	int prel = 0, prer = N-1;
	vector<int> l(N, 0), r(N, N-1)/*, m(N, N/2)*/;
	for(int i=0; i<N; i++){
		if(l[i] < r[i]) sex[mp(l[i], r[i])].pb(i);
	}
	int orig;
	while(sex.size()){
		/*cerr << '\n';
		for(int i=0; i<N; i++){
			cerr << i << ' ' << l[i] << ' ' << r[i] << '\n';
		}
		cerr << '\n';*/
		auto segp = sex.begin();
		auto seg = *segp;
		auto [cl, cr] = seg.fi;
		int cm = (cl + cr)/2;
		for(int i=cl; i<=cm; i++){
			if(i < prel || i > prer) orig = query(x[i]);
		}
		for(int i=prel; i<=prer; i++){
			if(i < cl || i > cm) orig = query(x[i]);
		}
		prel = cl;
		prer = cm;
		int lc = 0, rc = 0;
		for(auto i: seg.se){
			if(lc == cm-cl+1){
				l[i] = cm+1;
				rc++;
			}
			else if(rc == cr-cm){
				r[i] = cm;
				lc++;
			}
			else if(hint[i] <= cm){
				//cerr << "to the left (hint)";
				r[i] = cm;
				lc++;
			}
			else{
				//cerr << seg.fi.fi << ' ' << seg.fi.se << ' ' << m << '\n';
				//cerr << i << '\n';
				int cur = query(y[i]);
				/*for(int i=1; i<=2*N; i++){
					cerr << mmm[i];
				}*/
				//cerr << '\n';
				if(cur == orig){
					//cerr << "to the left";
					r[i] = cm;
					lc++;
				}
				else{
					//cerr << "to the right";
					l[i] = cm+1;
					rc++;
				}
				orig = cur;
				//query(y[i]);
				//cerr << ".\n";
			}
			if(l[i] < r[i]){
				sex[mp(l[i], r[i])].pb(i);
			}
		}
		sex.erase(segp);
	}
	/*for(int i=0; i<N; i++){
		cerr << y[i] << ' ' << x[l[i]] << '\n';
	}*/
	for(int i=0; i<N; i++){
		Answer(y[i], x[l[i]]);
	}
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:34:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |   if(x.size() == N){
      |      ~~~~~~~~~^~~~
minerals.cpp:98:5: warning: 'orig' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     if(cur == orig){
      |     ^~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10