Submission #1308247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308247		vako_p	Minerals (JOI19_minerals)	C++20	90 / 100	81 ms	8564 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,cntt = 0,last = 0;
bool vis[mxN],vis1[mxN];

ll query(ll i){
  cntt++;
	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);
  vector<ll> vv(2 * n);
  iota(vv.begin(), vv.end(), 1);
  random_device rd;
  mt19937_64 gen(rd());
  uniform_int_distribution<ll> dis(0, 2 * n - 1);
  for(int i = 0; i < 2 * n; i++) swap(vv[i], vv[dis(gen)]);
	for(auto i : vv){
		ll res = query(i);
		if(res == last){
      v[1].pb(i);
      l[i] = -1;
      ll sz = v[0].size();
      r[i] = sz - 1;
    } 
		else v[0].pb(i);
		last = res;
	}
	vector<vector<ll>> q(n + 5);
	for(auto i : v[1]){
		ll mid = l[i] + (r[i] - l[i]) / 2;
		if(r[i] > l[i] + 1) q[mid].pb(i);
    else vis1[r[i]] = true;
	}
	ll op = 0,cnt = n;
	while(cnt){
		if(op){
			for(int j = 0; j < n; j++){
				if(!vis1[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;
          if(r[i] <= l[i]){
            vis1[r[i]] = true;
            continue;
          }
          while(vis1[r[i]]) r[i]--;
          while(vis1[l[i] + 1]) l[i]++;
				  ll mid = l[i] + (r[i] - l[i]) / 2;
				  if(r[i] > l[i] + 1) q[mid].pb(i);
          else vis1[r[i]] = true;
				}
				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;
          if(r[i] <= l[i]){
            vis1[r[i]] = true;
            continue;
          }
          while(vis1[r[i]]) r[i]--;
          while(vis1[l[i] + 1]) l[i]++;
				  ll mid = l[i] + (r[i] - l[i]) / 2;
				  if(r[i] > l[i] + 1) q[mid].pb(i);
          else vis1[r[i]] = true;
				}
				q[j].clear();
				if(!vis1[j]) 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++;
			}
		}
	}
  // cout << cntt << " -- " << '\n';
	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: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10