QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488864#8819. CNOI Knowledgeyqh2025AC ✓112ms4100kbC++141.5kb2024-07-24 15:57:452024-07-24 15:57:47

Judging History

This is the latest submission verdict.

  • [2024-07-24 15:57:47]
  • Judged
  • Verdict: AC
  • Time: 112ms
  • Memory: 4100kb
Show
  • [2024-07-24 15:57:45]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
namespace SAM{
	struct hzzdj{
		int father,len;
		map<int,int>son;
	}hz[N<<1];
	int tot,last,ans;
	void init(){
		for(int i=0;i<=tot;i++){
			hz[i].son.clear();
			hz[i].father=hz[i].len=0;
		}
		hz[0].father=-1;last=tot=ans=0;
	}
	void insert(int cha){
		int p=last;
		int cur=++tot;hz[cur].len=hz[p].len+1;
		while(p!=-1&&!hz[p].son.count(cha)){
			hz[p].son[cha]=cur;
			p=hz[p].father;
		}
		if(p==-1)hz[cur].father=0;
		else{
			int q=hz[p].son[cha];
			if(hz[q].len==hz[p].len+1)hz[cur].father=q;
			else{
				int nq=++tot;hz[nq].len=hz[p].len+1;
				hz[nq].son=hz[q].son;
				hz[nq].father=hz[q].father;
				hz[q].father=hz[cur].father=nq;
				while(p!=-1&&hz[p].son[cha]==q){
					hz[p].son[cha]=nq;
					p=hz[p].father;
				}
			}
		}
		last=cur;
		ans+=hz[cur].len-hz[hz[cur].father].len;
	}
	int ask(){return ans;}
}
int n;
int ch[N],c;
int ask(int l,int r){
	cout<<"? "<<l<<" "<<r<<endl;
	int x;cin>>x;
	return x;
}
int solve(int l,int r){
//	cout<<l<<" "<<r<<endl;
	SAM::init();
	for(int i=l;i<=r;i++){
		SAM::insert(ch[i]);
	}
	return SAM::ask();
	return 0;
}
int main(){
	scanf("%d",&n);
	c=1;ch[1]=c;
	for(int i=2;i<=n;i++){
		int x=i;
		for(int j=9;j>=0;j--){
			int mid=x-(1<<j);
			if(mid<1)continue;
			int s1=solve(mid,i-1);
			int s2=ask(mid,i);
			if(s1+(i-1-mid+1+1)==s2)x=mid;
		}
		if(x==1)c++,ch[i]=c;
		else ch[i]=ch[x-1];
	}
	cout<<"! ";
	for(int i=1;i<=n;i++){
		cout<<ch[i]<<" ";
	}
	cout<<endl;
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

12
3
6
6
10
15
15
21
15
27
20
14
6
9
43
42
14
5
2
42
13
5
8
40
13
25
19

output:

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

result:

ok Accepted. 26 queries used.

Test #2:

score: 0
Accepted
time: 98ms
memory: 3824kb

input:

1000
3
5
2
3
2
11
5
7
11
5
2
11
3
2
11
5
7
34
11
5
3
33
11
5
2
31
11
3
2
29
9
3
2
29
5
3
2
27
5
3
2
23
5
3
2
23
9
13
15
108
23
11
5
3
108
27
11
5
3
108
31
11
5
2
108
33
11
3
2
110
34
11
5
7
112
34
11
5
2
113
34
12
5
8
113
33
12
5
2
113
32
12
5
8
115
31
12
5
2
115
28
12
5
8
115
31
11
5
3
115
32
11
5
...

output:

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

result:

ok Accepted. 8977 queries used.

Test #3:

score: 0
Accepted
time: 88ms
memory: 3776kb

input:

1000
2
3
2
5
7
11
5
2
11
3
2
11
5
7
11
5
2
33
11
3
2
33
9
3
2
31
5
3
2
27
5
3
2
23
5
3
2
23
9
13
15
23
11
5
2
28
12
5
8
107
31
12
5
2
107
32
11
3
2
105
32
9
3
2
103
32
9
20
14
99
32
11
5
2
103
33
11
3
2
105
32
9
3
2
107
29
5
3
2
109
31
9
17
11
109
31
11
5
2
112
31
12
5
8
113
31
12
5
2
113
32
12
5
8
...

output:

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

result:

ok Accepted. 8977 queries used.

Test #4:

score: 0
Accepted
time: 112ms
memory: 3888kb

input:

1000
3
5
3
5
2
11
5
8
12
5
2
12
5
8
12
5
2
33
11
3
2
32
11
5
7
33
11
5
3
34
11
5
3
34
11
5
2
34
11
3
2
33
9
3
2
31
5
3
2
116
27
5
3
2
113
23
5
3
2
109
17
5
3
2
109
17
57
35
26
109
23
11
5
3
108
27
11
5
2
105
29
11
3
2
101
29
9
3
2
97
29
9
19
14
93
29
11
5
3
92
29
11
5
2
89
29
11
3
2
92
29
11
5
7
93
...

output:

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

result:

ok Accepted. 8977 queries used.

Test #5:

score: 0
Accepted
time: 89ms
memory: 3772kb

input:

1000
2
3
2
5
7
11
5
3
11
5
2
11
3
2
9
3
2
29
5
3
2
27
5
3
2
27
9
13
20
28
11
5
2
28
12
5
8
31
11
5
3
32
11
5
2
31
11
5
8
111
28
11
5
3
112
27
11
5
3
112
29
9
5
3
111
29
9
5
3
111
31
11
5
2
113
31
11
5
8
113
31
12
5
2
111
33
12
5
8
110
33
12
5
2
111
31
12
5
8
113
31
11
5
3
113
32
11
5
2
111
31
11
5
8...

output:

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

result:

ok Accepted. 8977 queries used.

Test #6:

score: 0
Accepted
time: 71ms
memory: 3832kb

input:

1000
2
5
5
2
12
5
8
12
5
2
12
5
8
12
5
2
28
12
5
8
28
12
5
2
28
12
5
8
31
11
5
3
33
11
5
3
33
9
5
3
31
9
5
3
27
9
5
3
104
27
11
5
2
107
27
11
5
8
108
29
11
5
3
107
29
11
5
3
104
29
9
5
3
99
29
9
5
3
99
31
11
5
2
99
31
11
3
2
105
30
11
5
7
109
33
11
5
2
113
34
11
3
2
115
34
11
5
7
117
33
11
5
2
118
3...

output:

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

result:

ok Accepted. 8976 queries used.

Test #7:

score: 0
Accepted
time: 92ms
memory: 4100kb

input:

1000
3
5
2
3
2
12
11
5
2
11
3
2
11
5
7
36
11
5
3
33
11
5
2
31
11
3
2
32
50
61
35
11
5
3
36
11
5
3
37
11
5
2
37
13
23
29
129
37
13
5
3
129
37
11
5
3
128
35
9
5
3
125
33
9
5
3
124
29
9
5
3
125
29
69
47
38
125
29
13
6
9
125
32
12
6
9
123
33
12
6
9
122
35
13
5
3
121
35
13
6
9
122
36
13
6
9
124
38
13
5
2...

output:

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

result:

ok Accepted. 8974 queries used.

Test #8:

score: 0
Accepted
time: 86ms
memory: 4100kb

input:

1000
3
5
2
5
9
13
6
9
13
5
3
12
5
3
11
5
2
37
11
3
2
37
12
22
29
37
11
5
2
36
11
3
2
35
9
3
2
35
9
21
27
35
12
21
15
35
13
6
9
123
33
13
5
2
125
35
13
5
8
127
36
11
5
3
128
36
11
5
3
128
37
11
5
2
128
37
13
23
29
128
37
13
5
3
128
37
11
5
3
129
37
12
23
17
130
37
13
6
9
130
35
13
5
2
130
36
12
3
2
1...

output:

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

result:

ok Accepted. 8977 queries used.

Test #9:

score: 0
Accepted
time: 87ms
memory: 3844kb

input:

1000
3
6
5
2
13
5
8
12
5
2
13
24
18
13
5
2
39
13
24
18
39
13
5
3
38
11
5
3
37
12
23
17
37
13
5
2
37
12
3
2
35
9
3
2
32
5
3
2
125
29
5
3
2
120
24
5
3
2
118
24
65
43
33
117
24
64
42
33
117
29
13
6
9
116
32
13
5
2
115
33
13
5
9
115
35
13
5
2
115
35
11
3
2
115
37
11
5
7
117
37
11
5
2
117
35
12
5
8
119
3...

output:

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

result:

ok Accepted. 8976 queries used.

Test #10:

score: 0
Accepted
time: 90ms
memory: 3840kb

input:

1000
2
5
6
9
13
6
9
13
5
2
12
3
2
12
22
17
35
11
5
3
36
11
5
3
36
12
22
29
37
13
5
2
37
13
5
9
38
13
5
3
37
11
5
2
36
11
5
8
125
33
11
5
3
126
32
11
5
3
127
32
72
50
41
128
35
13
5
2
128
37
13
5
8
128
37
13
23
18
126
37
13
5
2
127
38
13
5
9
127
38
13
6
9
127
37
13
5
3
126
37
12
5
3
127
35
9
5
3
129
...

output:

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

result:

ok Accepted. 8976 queries used.

Test #11:

score: 0
Accepted
time: 98ms
memory: 3832kb

input:

1000
2
5
5
2
12
5
8
13
18
13
6
9
13
5
2
38
13
5
8
38
13
24
18
37
13
5
3
38
13
5
2
37
13
24
18
37
13
5
3
37
11
5
2
36
11
3
2
132
36
12
22
29
131
37
12
23
17
131
37
13
5
3
131
37
12
5
3
130
35
9
5
3
130
35
12
21
15
130
36
13
6
9
130
36
13
5
2
130
36
13
5
8
130
38
13
24
18
131
39
13
5
2
131
39
13
5
9
1...

output:

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

result:

ok Accepted. 8975 queries used.

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-08 16:50:44 | OpenSource Project