QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#288279#7510. Independent Set1kriWA 1ms4064kbC++142.5kb2023-12-22 13:21:362023-12-22 13:21:37

Judging History

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

  • [2023-12-22 13:21:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4064kb
  • [2023-12-22 13:21:36]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int cnt[4005][4005];
vector<int> qry(vector<int> c){
	int l=(int)c.size();
	cout<<"? "<<l<<' ';
	for (int i=0;i<l;i++)cout<<c[i]<<' ';
	cout<<endl;
	vector<int> ans(l);
	for (int i=0;i<l;i++)cin>>ans[i];
	return ans; 
}
namespace QwQ{
	vector<pair<int,int>> qwq[10005];
	void init(){
		for (int i=1;i<=10000;i++)qwq[i].clear();
		return;
	}
	vector<pair<int,int>> ask(vector<int> c,vector<pair<int,int>> d){
		int lc=(int)c.size(),ld=(int)d.size();
		vector<pair<int,int>> ans(ld);
		vector<int> awa;
		for (int i=0;i<lc;i++)awa.push_back(c[i]);
		for (int i=0;i<ld;i++)awa.push_back(d[i].first);
		vector<int> ovo=qry(awa);
		for (int i=0;i<ld;i++){
			ans[i].first=d[i].first,ans[i].second=ovo[lc+i];
			for (int j=0;j<i;j++)
				if (ovo[lc+j]==0)
					ans[i].second-=cnt[min(d[i].first,d[j].first)][max(d[i].first,d[j].first)];
		}
		return ans;
	}
	void work(int now,vector<int> c){
		int l=(int)c.size();
		if (l==0)return;
		if (l==1){
			for (int i=0;i<(int)qwq[now].size();i++)
				cnt[min(c[0],qwq[now][i].first)][max(c[0],qwq[now][i].first)]=qwq[now][i].second;
			return;
		}
		vector<int> cl,cr;
		for (int i=0;i<l/2;i++)cl.push_back(c[i]);
		for (int i=l/2;i<l;i++)cr.push_back(c[i]);
		vector<pair<int,int>> awa=ask(cl,qwq[now]);
		for (int i=0;i<(int)qwq[now].size();i++){
			if (awa[i].second>0)qwq[now*2].push_back(awa[i]);
			if (awa[i].second<qwq[now][i].second)
				qwq[now*2+1].push_back(make_pair(awa[i].first,qwq[now][i].second-awa[i].second));
		}
		work(now*2,cl);
		work(now*2+1,cr);
		return;
	}
}
void work(vector<int> c){
	int l=(int)c.size();
	if (l==0)return;
	if (l==1){
		cnt[c[0]][c[0]]=(qry({c[0],c[0]}))[1];
		return;
	}
	vector<int> a,b;
	vector<int> qwq=qry(c);
	for (int i=0;i<l;i++)
		if (qwq[i]==0)a.push_back(c[i]);
		else b.push_back(c[i]);
	work(b);
	int la=(int)a.size(),lb=(int)b.size();
	c.clear();
	for (int i=0;i<la;i++)c.push_back(a[i]); 
	for (int i=0;i<lb;i++)c.push_back(b[i]);
	qwq=qry(c);
	QwQ::init();
	for (int i=0;i<lb;i++)QwQ::qwq[1].push_back(make_pair(b[i],qwq[la+i]));
	QwQ::work(1,a);
	return; 
}
int main(){
	int n;
	cin>>n;
	vector<int> c;
	for (int i=1;i<=n;i++)c.push_back(i);
	work(c);
	int m=0;
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			m+=cnt[i][j];
	cout<<"! "<<m<<' ';
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++)
			while(cnt[i][j]--)cout<<i<<' '<<j<<' ';
	cout<<endl;
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4064kb

input:

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

output:

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

result:

wrong answer Wrong graph