QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288099#7510. Independent Set1kriWA 1ms3672kbC++141.7kb2023-12-21 20:52:062023-12-21 20:52:06

Judging History

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

  • [2023-12-21 20:52:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3672kb
  • [2023-12-21 20:52:06]
  • 提交

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})[0];
		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: 0
Wrong Answer
time: 1ms
memory: 3672kb

input:

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

output:

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

result:

wrong answer Wrong graph