QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188883#7510. Independent Setzhoukangyang#TL 0ms0kbC++112.9kb2023-09-26 16:07:392023-09-26 16:07:39

Judging History

你现在查看的是最新测评结果

  • [2023-09-26 16:07:39]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-09-26 16:07:39]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 1 << 20;
mt19937_64 orz;

int n, m;
vi e[N];

int ind[N], ord[N], top;
int dp[N], lst[N];

vector < pair < int, int > > ans;

int hm[N];
vi re[N];
vi qry(vi S) {
	cout << "? ";
	for(auto&u : S) {
		cout << u << ' ';
	}
	cout << endl;
	
//	vi ans;
//	for(auto&p : S) {
//		int cnt = 0;
//		for(auto&v : re[p]) {
//			cnt += hm[v];
//		}
//		ans.emplace_back(cnt);
//		if(!cnt) 
//			hm[p] = 1;
//	}
//	for(auto&p : S) 
//		hm[p] = 0;
//	cout << "ans = ";
//	for(auto&u : ans) cout << u << ' ';
//	cout << endl;
//	return ans;
	
	vi ret(sz(S));
	L(i, 0, sz(ret) - 1) {
		cin >> ret[i];
	}
	return ret;
}

vector < pair < int, int > > nans;
void slv(vi S, vi T, vi cnt) {
	if(sz(S) == 1) {
		L(i, 0, sz(T) - 1) 
			L(j, 1, cnt[i]) 
				nans.emplace_back(S[0], T[i]), 
				cout << "add 1" << endl; 
		return ;
	}
	vi rT, rcnt;
	L(i, 0, sz(T) - 1) {
		if(cnt[i] == 0) 
			continue;
		rT.emplace_back(T[i]);
		rcnt.emplace_back(cnt[i]);
	}
	swap(T, rT), rT.clear();
	swap(cnt, rcnt), rcnt.clear();
	
	int mid = sz(S) / 2;
	vi tmp;
	L(i, 0, mid - 1) 
		tmp.emplace_back(S[i]);
	L(i, 0, sz(T) - 1) 
		tmp.emplace_back(T[i]);
	vi rm = qry(tmp);
	L(z, mid, sz(rm) - 1) {
		int ins = !rm[z];
		int u = tmp[z];
		for(auto &v : e[u]) rm[z] -= hm[v];
		if(ins) hm[u] = true;
	}
	
	vi cntl(sz(T)), cntr(sz(T));
	L(i, 0, sz(T) - 1) {
		cntl[i] = rm[i + mid];
		cntr[i] = cnt[i] - cntl[i];
	}
	vi Sl, Sr;
	L(i, 0, sz(S) - 1) {
		if(i < mid) {
			Sl.emplace_back(S[i]);
		} else {
			Sr.emplace_back(S[i]);
		}
	}
	
	slv(Sl, T, cntl);
	slv(Sr, T, cntr); 
}

void work(vi S) {
	if(sz(S) <= 1) {
		return ;
	}
	
	vi T = qry(S);
	vi st, nt, cnt;
	L(i, 0, sz(T) - 1) {
		if(T[i] == 0) {
			st.emplace_back(S[i]);
		} else {
			nt.emplace_back(S[i]);
			cnt.emplace_back(T[i]);
		}
	}
	work(nt);
	
	nans.clear();
	slv(st, nt, cnt);
	for(auto &z : nans) {
		int u = z.first;
		int v = z.second;
		ans.emplace_back(z);
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
}

void Add(int u, int v) {
	re[u].emplace_back(v);
	re[v].emplace_back(u);
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	Add(1, 2);
	Add(1, 2);
	Add(1, 3);
	Add(4, 4);
	Add(4, 5);
	
	cin >> n;
	
	vi S;
	L(i, 1, n) S.emplace_back(i);
	shuffle(S.begin(), S.end(), orz);
	
	work(S);
	L(i, 1, n) {
		vi qwq = qry(vi{i, i});
		if(qwq[1]) 
			ans.emplace_back(make_pair(i, i));
	}
	cout << "! ";
	cout << sz(ans) << ' ';
	for(auto u : ans) 
		cout << u.first << ' ' << u.second << ' ';
	cout << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4
0 2 0

output:

? 3 2 1 4 

result: