QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#489360#8819. CNOI Knowledgec20150005WA 264ms34560kbC++141.1kb2024-07-24 19:45:492024-07-24 19:45:49

Judging History

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

  • [2024-07-24 19:45:49]
  • 评测
  • 测评结果：WA
  • 用时：264ms
  • 内存：34560kb
查看
  • [2024-07-24 19:45:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){int f=1;while(!isdigit(c))f=(c^'-'?1:-1),c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x*f;}
const int N=1e3+3;
int n,a[N],s[N],S,c[N];
using ull=unsigned long long;
const ull pw=19260817;
ull h[N];
map<ull,int> mp;
int main(){
	n=rd();a[1]=s[1]=h[1]=++S;
	for(int i=2;i<=n;i++){
		memset(c,0,sizeof c);
		int l=2,r=i,p=0;
		while(l<=r){
			int mid=(l+r)>>1;
			cout<<"? "<<mid<<" "<<i<<endl;
			int x=rd();
//			cout<<"? "<<mid<<" "<<i-1<<endl;
//			int y=rd(); 
			if(x==s[mid]+i-mid+1)r=mid-1;
			else p=mid,l=mid+1;
		}
		if(p==0)a[i]=++S;
		else a[i]=a[p];
		ull x=0;
		for(int j=i;j;j--){
			x=x*pw+a[j];
			c[mp[x]+1]++;c[j+1]--;
			mp[x]=j;
		}
		for(int j=1;j<=i;j++)c[j]+=c[j-1],s[j]+=c[j];
//		for(int j=1;j<=i+1;j++)c[j]=0;
//		cerr<<"I: "<<i<<endl;
//		for(int j=1;j<=i;j++)cerr<<s[j]<<" ";
//		cerr<<endl;
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)printf("%d ",a[i]);
	cout<<endl;
	return 0;
}
/*

1 2 3 4 5 6 2 5 7 7 5 6 
*/
源文件, 语言: C++14

詳細信息

Test #1:

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

input:

12
1
3
3
6
6
10
6
15
10
20
15
9
3
6
14
27
34
14
5
2
1
19
5
13
8
19
40
31
25

output:

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

result:

ok Accepted. 29 queries used.

Test #2:

score: -100
Wrong Answer
time: 264ms
memory: 34560kb

input:

1000
1
2
1
2
1
5
7
5
2
1
7
2
1
7
16
11
11
5
3
11
5
2
1
15
3
2
1
14
3
2
1
17
4
2
1
13
4
2
1
15
4
2
1
15
47
31
23
23
11
5
3
27
11
5
3
36
11
5
2
1
39
11
3
2
1
48
15
5
11
7
50
16
5
2
1
59
16
5
12
8
59
16
5
2
1
69
20
8
3
5
67
20
8
2
1
76
20
8
3
5
76
21
8
3
5
88
26
8
2
1
87
24
8
3
5
98
24
8
2
1
96
26
7
2
...

output:

? 2 2
? 2 3
? 3 3
? 3 4
? 4 4
? 3 5
? 2 5
? 4 6
? 5 6
? 6 6
? 4 7
? 6 7
? 7 7
? 5 8
? 3 8
? 4 8
? 5 9
? 7 9
? 8 9
? 6 10
? 8 10
? 9 10
? 10 10
? 6 11
? 9 11
? 10 11
? 11 11
? 7 12
? 10 12
? 11 12
? 12 12
? 7 13
? 10 13
? 12 13
? 13 13
? 8 14
? 11 14
? 13 14
? 14 14
? 8 15
? 12 15
? 14 15
? 15 15
? 9...

result:

wrong answer Wrong Answer.
English 繁體中文 简体中文

伺服器時間: 2025-02-02 05:57:27 | 開源專案