QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489451#8819. CNOI Knowledge123456xwdWA 0ms3760kbC++141.1kb2024-07-24 20:20:232024-07-24 20:20:25

Judging History

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

  • [2024-07-24 20:20:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3760kb
  • [2024-07-24 20:20:23]
  • 提交

answer

#include<bits/stdc++.h>
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define mid ((l+r)>>1) 
#define ls k<<1
#define rs k<<1|1
#define int long long
#define ull unsigned long long
using namespace std;
inline int rd(){
	int x=0,f=1; char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	return x*f;
}
const int N=1000+5,INF=0x3f3f3f3f3f3f3f3f;
const ull p=13331;
int a[N],n,tot;
map<ull,int> mp;
int c[N],sum[N];

signed main(){
	n=rd();
	sum[1]=a[1]=++tot,mp[1]=1;
	for(int i=2;i<=n;i++){
		int tmp,l=1,r=i,p=1;
		while(l<=r){
			printf("? %lld %lld\n",mid,i);fflush(stdout);
			tmp=rd();
			if(tmp==sum[mid]+mid-i+1){
				p=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		if(p==1) a[i]=++tot;
		else a[i]=a[p-1];
		
		memset(c,0,sizeof(c));
		ull Hash=0;
		for(int j=i;j>=1;j--){
			Hash=Hash*p+a[j];
			c[mp[Hash]+1]++,c[j+1]--;
			mp[Hash]=j;
		}
		for(int j=1;j<=i;j++) c[j]+=c[j-1],sum[j]+=c[j];
	}
	printf("! ");
	for(int i=1;i<=n;i++) printf("%lld ",a[i]);
	fflush(stdout);
	return 0;	
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3760kb

input:

12
3
1
3
1
6
3
1
6
3
1
10
3
1
10
3
1
14
6
3
1
14
6
3
1
19
5
2
1
19
5
3
1
25
9
3
1

output:

? 1 2
? 2 2
? 2 3
? 3 3
? 2 4
? 3 4
? 4 4
? 3 5
? 4 5
? 5 5
? 3 6
? 5 6
? 6 6
? 4 7
? 6 7
? 7 7
? 4 8
? 6 8
? 7 8
? 8 8
? 5 9
? 7 9
? 8 9
? 9 9
? 5 10
? 8 10
? 9 10
? 10 10
? 6 11
? 9 11
? 10 11
? 11 11
? 6 12
? 9 12
? 11 12
? 12 12
! 1 1 1 1 1 1 1 1 1 1 1 1 

result:

wrong answer Wrong Answer.