QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488728#8819. CNOI Knowledgesumi007WA 1ms6708kbC++23716b2024-07-24 14:42:032024-07-24 14:42:03

Judging History

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

  • [2024-07-24 14:42:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6708kb
  • [2024-07-24 14:42:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N = 2077;
int n,s[N],cnt,val[N][N];
int ask(int l,int r){
	if(val[l][r]) return val[l][r];
	cout << "? " << l << ' ' << r << "\n",cout.flush();
	cin >> val[l][r];
	return val[l][r];
}
int main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0); 
	cin >> n;
	for(int i=1;i<=n;i++){
		int l = 1,r = i-1,las = i-1;
		while(l<=r){
			int mid = (l+r)>>1;
			if(ask(mid,i-1)+i-mid+1==ask(mid,i)){
				las = mid-1;
				r = mid-1;
			}else{
				l = mid+1;
			}
		}
		if(las == 0) s[i] = ++cnt;
		else s[i] = s[las];
	}
	cout << "! ";
	for(int i=1;i<=n;i++) cout << s[i] << ' ';
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

12
1
3
6
3
6
10
10
15
6
10
21
15
27
15
20
10
14
3
6
6
9
20
26
34
34
43
14
19
6
9
3
5
1
2
25
8
5
19
25
9
13
19

output:

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

result:

ok Accepted. 42 queries used.

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 6708kb

input:

1000
1
3
5
1
2
3
1
2
7
7
11
5
8
3
5
1
2
11
3
1
2
7
11
5
7
15
8
3
5
1
3
11
15
8
5
1
2
19
7
3
1
2
15
19
4
3
1
2
23
5
3
1
2
17
20
4
5
3
1
2
23
4
5
3
1
2
15
23
4
9
6
13
7
15
31
14
5
8
3
5
1
3
23
31
11
15
7
5
1
3
41
11
16
8
5
1
2
36
45
11
15
7
3
1
2
55
20
7
11
15
11
48
58
21
5
8
3
5
1
2
68
16
21
8
5
59
6...

output:

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

result:

wrong answer Too many queries.