Submission #1226169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226169		ansori	Minerals (JOI19_minerals)	C++20	40 / 100	313 ms	11344 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int n){
	long long x = rng();
	return abs(x) % n;
}
void Answer(int x, int y);
int Query(int x);
vector<pair<vector<int> , vector<int>>> vec;
set<int> st;
int lst;
int ask(int x){
	lst = Query(x);
	if(st.find(x) == st.end()) st.insert(x);
	else st.erase(x);
	//for(auto to : st) cout << to << ' ';
	//cout << '\n';
	return lst;
}
void clr(){
	for(auto to : st) ask(to);
	st.clear();
	return ;
}
void f(vector<int> v){
	if(v.size() == 0){
		return ;
	}
	if(v.size() == 2){
		vec.push_back({{v[0]} , {v[1]}});
		return ;
	}
	for(auto to : v){
		// cout << to << ' ';
	}
	//cout << '\n';
	int sz = v.size();
	set<int> s1 , s2;
	for(int i = 0;i < sz / 2; ++ i){
		s1.insert(v[i]);
		if(st.find(v[i]) == st.end()) ask(v[i]);
	}
	for(int i = sz / 2; i < sz; ++ i) s2.insert(v[i]);
	for(auto to : s2){
		if(st.find(to) != st.end()) ask(to);
	}
	vector<int> nv1 , nv2 , v1 , v2;
	for(auto to : s2){
		int ls = lst , x = ask(to);
		if(ls == x) {
			v2.push_back(to);
		}
		else{
			nv2.push_back(to);
			ask(to);
		}
	}
	for(auto to : s1) ask(to);
	for(auto to : s1){
		int ls = lst , x = ask(to);
		if(ls == x){
			v1.push_back(to);
		}
		else{
			nv1.push_back(to);
			ask(to);
		}
	}
	//cout << v1.size() << ' ' << v2.size() << '\n';
	vec.push_back({v1 , v2});
	f(nv2) , f(nv1);
}
void ans(vector<int> p , vector<int> q){
	if(p.size() == 0) return ;
	if(p.size() == 1){
		Answer(p[0] , q[0]);
		return ;
	}
	int sz = p.size();
	set<int> s1 , s2;
	vector<int> np1 , nq1 , np2 , nq2;
	for(int i = 0;i < sz / 2; ++ i){
		if(st.find(q[i]) == st.end()) ask(q[i]);
		nq1.push_back(q[i]);
	}
	for(int i = sz / 2; i < sz; ++ i){
		if(st.find(q[i]) != st.end()) ask(q[i]);
		nq2.push_back(q[i]);
	}
	for(int i = 0; i < sz; ++ i){
		int ls = lst , nw = ask(p[i]);
		if(ls == nw) np1.push_back(p[i]);
		else np2.push_back(p[i]);
	}
	//cout << -1;
	ans(np1 , nq1);
	ans(np2 , nq2);
}
void Solve(int N) {
  vector<int> ff;
  for(int i = 1;i <= 2 * N; ++ i) ff.push_back(i);
  for(int i = 0;i < 2 * N; ++ i) swap(ff[i] , ff[rand(2 * N)]);
  f(ff);
  for(auto to : vec){
  	ans(to.fi , to.se);
  }
}

• 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