Submission #1226180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226180		ansori	Minerals (JOI19_minerals)	C++20	80 / 100	320 ms	7728 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 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> a , b;
  for(int i = 1;i <= 2 * N; ++ i){
	int ls = lst , x = ask(i);
  	if(ls != x) a.push_back(i);
  	else b.push_back(i);
  }
  for(int i = 0;i < a.size(); ++ i){
	swap(a[i] , a[rand(N)]);
	swap(b[i] , b[rand(N)]);
  }
  vec.push_back({a , b});
  for(auto to : vec){
  	ans(to.fi , to.se);
  }
}

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10