QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288104#7510. Independent Set1kriWA 64ms64892kbC++141.7kb2023-12-21 21:18:422023-12-21 21:18:44

Judging History

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

  • [2023-12-21 21:18:44]
  • 评测
  • 测评结果:WA
  • 用时:64ms
  • 内存:64892kb
  • [2023-12-21 21:18:42]
  • 提交

answer

#include <iostream>
#include <cstdio> 
#include <algorithm>
#include <vector>
using namespace std;
vector<int> ask(vector<int> a){
	int l=(int)a.size();
	cout<<"? "<<l<<' ';
	for (int i=0;i<l;i++)cout<<a[i]<<' ';
	cout<<endl;
	vector<int> ans(l);
	for (int i=0;i<l;i++)cin>>ans[i];
	return ans;
}
int cnt[4005][4005];
vector<pair<int,int>> qwq[10005];
void work(int now,int l,int r){
	if (l==r){
		for (int i=0;i<(int)qwq[now].size();i++)
			cnt[l][qwq[now][i].first]=qwq[now][i].second;
		cnt[l][l]=ask({l,l})[1];
		return;
	}
	int mid=(l+r)/2;
	vector<int> ovo;
	for (int i=l;i<=mid;i++)ovo.push_back(i);
	for (int i=0;i<(int)qwq[now].size();i++)ovo.push_back(qwq[now][i].first);
	vector<int> awa=ask(ovo);
	sort(qwq[now].begin(),qwq[now].end());
	for (int i=0;i<(int)qwq[now].size();i++){
		int p=awa[mid-l+1+i];
		for (int j=0;j<i;j++)p-=cnt[qwq[now][j].first][qwq[now][i].first];
		if (p>0)qwq[now*2].push_back(make_pair(qwq[now][i].first,p));
		if (p<qwq[now][i].second)qwq[now*2+1].push_back(make_pair(qwq[now][i].first,qwq[now][i].second-p));
	}
	work(now*2+1,mid+1,r);
	ovo.clear(),awa.clear();
	for (int i=l;i<=r;i++)ovo.push_back(i);
	awa=ask(ovo);
	for (int i=0;i<r-mid;i++){
		int p=awa[mid-l+1+i];
		for (int j=0;j<i;j++)p-=cnt[mid+1+j][mid+1+i];
		if (p>0)qwq[now*2].push_back(make_pair(mid+1+i,p));
	}
	work(now*2,l,mid);
	return;
} 
int main(){
	int n;
	cin>>n;
	work(1,1,n);
	int m=0;
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=1;k<=cnt[i][j];k++)
				m++;
	cout<<"! "<<m<<' ';
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			for (int k=1;k<=cnt[i][j];k++)
				cout<<i<<' '<<j<<' ';
	cout<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5780kb

input:

4
0 2
0
0 1
0 0
0 0
0 2 1 0
0 1
0 0
0 2
0 0

output:

? 2 1 2 
? 1 3 
? 2 4 4 
? 2 3 4 
? 2 3 3 
? 4 1 2 3 4 
? 2 1 3 
? 2 2 2 
? 2 1 2 
? 2 1 1 
! 4 1 2 1 2 1 3 4 4 

result:

ok Ok, Accepted!

Test #2:

score: -100
Wrong Answer
time: 64ms
memory: 64892kb

input:

4000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0...

output:

? 2000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

wrong answer Wrong graph