QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769842#7510. Independent SetmaxyzfjTL 1ms3964kbC++144.2kb2024-11-21 19:34:422024-11-21 19:34:44

Judging History

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

  • [2024-11-21 19:34:44]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3964kb
  • [2024-11-21 19:34:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
#define mp(x,y) make_pair(x,y)
#define lb(x) (x&(-x))
#define fi first
#define se second
#define pii pair<int,int>
#define piii pair<int,pair<int,int> >
int read(){
	int x=0,f=1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
    	if(ch=='-')f=-1;
		ch=getchar();
    }
	while(ch>='0'&&ch<='9'){
    	x=x*10+ch-48;
		ch=getchar();
    }
	return x*f;
}
void writ(int x){
    if(x<0){
		putchar('-'),x=-x;
	}
    if(x>9){
		writ(x/10);
	}
    putchar(x%10 +'0');
}
void write(int x,char p=' '){
    writ(x);
    putchar(p);
}
string sread(){
    string t="";
    char c=getchar();
    while(c==' '||c=='\t'||c=='\r'||c=='\n'||c==0||c==EOF){
        c=getchar();
    }
    while(!(c==' '||c=='\t'||c=='\r'||c=='\n'||c==0||c==EOF)){
        t+=c,c=getchar();
    }
    return t;
}
const int QMR=1000000007,LSJ=998244353,inf=2e9+31,N=4005;
//int cal(int a,int b=QMR-2){
//	int base=a,ret=1;
//	while(b){
//		if(b&1){
//			ret=ret*base%QMR;
//		}
//		base=base*base%QMR;
//		b>>=1;
//	}
//	return ret;
//}
mt19937 rnd(time(0)^clock());
int n,a[N];
//map<basic_string<short>,basic_string<short> >h;
//void query(basic_string<short>t){
////	if(h.find(t)!=h.end())return h[t];
//	cout<<"? ";
//	write(t.size());
//	for(int i:t)write(i);
//	cout<<endl;
//}
int cnt=0;
basic_string<short>ans[N],b[N],qmr;
void work(int k,int l,int r,basic_string<short>s){
	if(s.size()==0)return;;
	if(l==r){
		s=b[k][l]+s;
//		basic_string<short>lsj=query(s);
		cout<<"? "<<s.size()<<" ";
		for(int i:s)cout<<i<<" ";
		cout<<endl;
		basic_string<short>lsj;
		for(int i=0;i<s.size();i++){
			int t=read();lsj+=t;
		}
		for(int i=1;i<lsj.size();i++){
			if(lsj[i]-ans[s[i]].size()>0){
//				cout<<lsj[i]<<" "<<s[i]<<" "<<ans[s[i]].size()<<endl;
				int tt=lsj[i]-ans[s[i]].size();
				for(int j=1;j<=tt;j++)ans[s[i]]+=b[k][l];
			}
		}
		return;
	}
	int mid=(l+r)>>1;
	basic_string<short>L,R,ll,rr;
	for(int i=l;i<=mid;i++){
		L+=b[k][i];
	}
	for(int i=mid+1;i<=r;i++){
		R+=b[k][i];
	}
	cout<<"? "<<L.size()+s.size()<<" ";
	for(int i:L)cout<<i<<" ";
	for(int i:s)cout<<i<<" ";
	cout<<endl;
	basic_string<short>lsj;
	for(int i=0;i<L.size()+s.size();i++){
		int t=read();lsj+=t;
	}
	for(int i=L.size();i<lsj.size();i++){
		if(lsj[i]-ans[s[i-L.size()]].size()>0){
			ll+=s[i-L.size()];
		}
	}
	lsj.clear();
	cout<<"? "<<R.size()+s.size()<<" ";
	for(int i:R)cout<<i<<" ";
	for(int i:s)cout<<i<<" ";
	cout<<endl;
	for(int i=0;i<R.size()+s.size();i++){
		int t=read();lsj+=t;
	}
	for(int i=R.size();i<lsj.size();i++){
		if(lsj[i]-ans[s[i-R.size()]].size()>0){
			rr+=s[i-R.size()];
		}
	}
	L.clear();R.clear();
	work(k,l,mid,ll);
	ll.clear();
	work(k,mid+1,r,rr);rr.clear();
}
signed main(){
    //freopen("qmr.in","r",stdin);
    //freopen("qmr.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    n=read();
    basic_string<short>g;
    for(int i=1;i<=n;i++)g+=i;
    while(g.size()){
    	cnt++;
		cout<<"? "<<g.size()<<" ";
		for(int i:g)cout<<i<<" ";
		cout<<endl;
    	basic_string<short>tt,c,d;
		for(int i=0;i<g.size();i++){
			int t=read();tt+=t;
		}
    	for(int i=0;i<tt.size();i++){
    		if(tt[i]!=0)c+=g[i];
    		else b[cnt]+=g[i];
		}
		g=c;
	}
	basic_string<short>tmp=b[cnt];
	for(int i=cnt-1;i>=1;i--){
//		query(b[i]+b[i]+tmp);
		cout<<"? "<<b[i].size()+tmp.size()<<" ";
		for(int j:b[i])cout<<j<<" ";
		for(int j:tmp)cout<<j<<" ";
		cout<<endl;
		qmr.clear();
		for(int j=0;j<b[i].size()+tmp.size();j++){
			int t=read();qmr+=t;
		}
		for(int j=0;j<b[i].size();j++){
//			cout<<j<<" "<<qmr[j]<<endl;
			a[b[i][j]]+=qmr[j];
		}
		basic_string<short>pmt;
		for(int j=b[i].size();j<qmr.size();j++){
			if(qmr[j]){
				pmt+=tmp[j-b[i].size()];
			}
		}
//		for(int j:pmt)cout<<j<<" ";
//		cout<<endl;
		work(i,0,b[i].size()-1,pmt);
		tmp+=b[i];b[i].clear();
	}
//	if(n==4000)return 0;
	int m=0;
	for(int i=1;i<=n;i++){
		cout<<"? 2 "<<i<<" "<<i<<endl;
		int t=read();a[i]=read();
		for(int j=1;j<=a[i];j++)ans[i]+=i;
		m+=ans[i].size();
	}
	cout<<"! "<<m<<" ";
	for(int i=1;i<=n;i++){
		for(int j:ans[i])cout<<i<<" "<<j<<" ";
	}
	cout<<endl;
	return 0;
}



详细

Test #1:

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

input:

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

output:

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

result:

ok Ok, Accepted!

Test #2:

score: -100
Time Limit Exceeded

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:

? 4000 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: