Submission #1308234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308234		vako_p	Minerals (JOI19_minerals)	C++20	40 / 100	22 ms	10088 KiB

minerals

#include "minerals.h"	
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
	
const int mxN = 1e5 + 5;
static ll n,last = 0;
bool vis[mxN];

ll query(ll i){
	ll res = Query(i);
	vis[i] = 1 - vis[i];
	return res;
}

void Solve(int N){
	n = N;	
	vector<ll> v[2],l(2 * n + 5),r(2 * n + 5);
	for(int i = 1; i <= 2 * n; i++){
		ll res = query(i);
		if(res == last) v[1].pb(i);
		else v[0].pb(i);
		last = res;
	}
	vector<vector<ll>> q(n + 5);
	for(auto i : v[1]){
		l[i] = -1;
		r[i] = n - 1;
		ll mid = l[i] + (r[i] - l[i]) / 2;
		if(r[i] > l[i] + 1) q[mid].pb(i);
	}
	ll op = 0,cnt = n;
	while(cnt){
		if(op){
			for(int j = 0; j < n; j++){
				last = query(v[0][j]);
				for(auto i : q[j]){
					ll res = query(i);
					if(res == last) r[i] = j;
					else l[i] = j;
					last = res;
				}
				q[j].clear();
			}
		}
		else{
			for(int j = n - 1; j >= 0; j--){
				for(auto i : q[j]){
					ll res = query(i);
					if(res == last) r[i] = j;
					else l[i] = j;
					last = res;
				}
				q[j].clear();
				last = query(v[0][j]);
			}
		}
    op = 1 - op;
		cnt = 0;
		for(auto i : v[1]){
      // cout << i << ' ' << l[i] << ' ' << r[i] << '\n';
			if(r[i] > l[i] + 1){
				cnt++;
				ll mid = l[i] + (r[i] - l[i]) / 2;
				q[mid].pb(i);
			}
		}
	}
	for(auto i : v[1]) Answer(i, v[0][r[i]]);
}

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