QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489116#8819. CNOI Knowledgeran_qwqAC ✓23ms7704kbC++232.3kb2024-07-24 18:12:122024-07-24 18:12:16

Judging History

This is the latest submission verdict.

  • [2024-07-24 18:12:16]
  • Judged
  • Verdict: AC
  • Time: 23ms
  • Memory: 7704kb
  • [2024-07-24 18:12:12]
  • Submitted

answer

#include<bits/stdc++.h>
#define il inline
#define ui unsigned int
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define ldb long double
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define fir first
#define sec second
#define gc getchar
#define pc putchar
#define mst(a,x) memset(a,x,sizeof a)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pct __builtin_popcount
using namespace std;
const int N=1010,INF=0x3f3f3f3f,MOD=1e9+7; const ll INFll=0x3f3f3f3f3f3f3f3f;
il int rd() {int x=0,f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il ll rdll() {ll x=0; int f=1; char ch=gc(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f;}
il void wr(int x) {if(x<-2147483647) {printf("-2147483648"); return;} if(x<0) {pc('-'),wr(-x); return;} if(x<10) {pc(x+'0'); return;} wr(x/10),pc(x%10+'0');}
il void wrll(ll x) {if(x<-9223372036854775807) return (void)printf("-9223372036854775808"); if(x<0) return pc('-'),wrll(-x); if(x<10) return (void)pc(x+'0'); wrll(x/10),pc(x%10+'0');}
il void wr(int x,char *s) {wr(x),printf("%s",s);}
il void wrll(ll x,char *s) {wrll(x),printf("%s",s);}
il int vmod(int x) {return x>=MOD?x-MOD:x;}
il int vadd(int x,int y) {return vmod(x+y);}
il int vsub(int x,int y) {return vmod(x-y+MOD);}
il int vmul(int x,int y) {return 1ll*x*y%MOD;}
il int qpow(int x,int y) {int res=1; for(;y;y>>=1,x=vmul(x,x)) if(y&1) res=vmul(res,x); return res;}
il void cadd(int &x,int y) {x=vmod(x+y);}
il void csub(int &x,int y) {x=vmod(x-y+MOD);}
il void cmax(int &x,int y) {x<y&&(x=y);}
il void cmin(int &x,int y) {x>y&&(x=y);}
int n,cnt,a[N],b[N],ne[N][N];
int qry(int l,int r) {printf("? "),wr(l," "),wr(r,"\n"),fflush(stdout); return rd();}
void QwQ() {
	n=rd(),cnt=a[1]=b[1]=1;
	for(int i=2,l,r,mid,mx;i<=n;i++) {
		for(l=1,r=i-1;l<=r;) mid=l+r>>1,qry(mid,i)==b[mid]+i+1-mid?r=mid-1:l=mid+1;
		mx=0,a[i]=!r?++cnt:a[r],b[i]=1;
		for(int j=i-1,k;j;j--) {
			k=ne[j][i-1]; while(k&&a[i]!=a[j+k]) k=ne[j][j+k-1];
			if(a[i]==a[j]||k) ne[j][i]=k+1; b[j]+=i+1-(mx=max(mx,ne[j][i]))-j;
		}
	}
	printf("! "); for(int i=1;i<=n;i++) wr(a[i]," "); puts(""),fflush(stdout);
}
signed main() {
	int T=1; while(T--) QwQ();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

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

result:

ok Accepted. 27 queries used.

Test #2:

score: 0
Accepted
time: 20ms
memory: 7700kb

input:

1000
3
5
2
3
2
7
11
8
5
2
11
3
2
11
5
7
15
8
5
3
15
8
5
2
19
7
3
2
19
4
3
2
23
5
3
2
20
5
3
2
23
5
3
2
23
9
13
15
31
14
8
5
3
31
15
7
5
3
41
16
8
5
2
45
15
7
3
2
55
20
7
15
11
58
21
8
5
2
68
21
8
5
69
21
8
5
2
80
26
12
5
8
79
24
12
5
2
89
24
12
5
8
87
26
11
5
3
100
32
11
5
2
100
31
11
5
8
112
31
12
...

output:

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

result:

ok Accepted. 8880 queries used.

Test #3:

score: 0
Accepted
time: 10ms
memory: 7704kb

input:

1000
2
3
2
5
7
8
5
2
7
3
2
11
5
7
11
5
2
15
7
3
2
14
4
3
2
17
4
3
2
13
4
3
2
15
5
3
2
15
51
32
23
23
11
5
2
28
12
5
8
36
16
8
5
2
38
16
7
3
2
45
14
4
3
2
44
14
7
9
50
20
8
5
2
54
19
7
3
2
64
19
4
3
2
65
17
4
3
2
76
24
9
17
11
76
24
11
5
2
88
24
12
5
8
87
26
12
5
2
100
32
12
5
8
102
33
11
5
3
116
32
...

output:

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

result:

ok Accepted. 8879 queries used.

Test #4:

score: 0
Accepted
time: 20ms
memory: 7544kb

input:

1000
3
5
3
5
2
8
5
8
5
2
12
5
8
12
5
2
16
7
3
2
16
7
11
21
8
5
3
20
7
5
3
27
11
5
2
27
11
3
2
33
9
3
2
31
5
3
2
36
6
4
3
2
31
6
4
3
2
35
6
4
3
2
35
11
17
26
44
17
8
5
3
44
19
8
5
2
53
19
7
3
2
53
19
4
3
2
62
24
9
19
14
63
24
11
5
3
71
24
11
5
2
69
24
11
3
2
81
29
11
5
7
81
27
11
5
3
96
30
11
5
3
99
...

output:

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

result:

ok Accepted. 8882 queries used.

Test #5:

score: 0
Accepted
time: 18ms
memory: 7680kb

input:

1000
2
3
2
5
7
8
5
3
8
5
2
11
3
2
9
3
2
11
4
3
2
6
4
3
2
13
34
27
20
17
8
5
2
24
12
5
8
26
11
5
3
32
11
5
2
31
11
5
8
36
14
8
5
3
36
15
7
5
3
44
14
7
5
3
41
11
7
5
3
52
17
8
5
2
55
19
8
5
65
21
8
5
2
65
21
8
5
76
26
12
5
2
75
24
12
5
8
87
26
11
5
3
87
26
11
5
2
98
31
11
5
8
95
31
12
5
2
105
31
12
5
...

output:

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

result:

ok Accepted. 8863 queries used.

Test #6:

score: 0
Accepted
time: 12ms
memory: 7628kb

input:

1000
2
5
5
2
8
5
8
5
2
12
5
8
12
5
2
16
8
5
16
8
5
2
20
8
5
21
8
5
3
27
11
5
3
26
9
5
3
31
9
5
3
27
9
5
3
34
14
8
5
2
34
15
8
5
41
14
8
5
3
41
15
7
5
3
48
19
7
5
3
48
17
7
5
3
60
17
8
5
2
63
19
7
3
2
75
25
11
5
7
77
27
11
5
2
90
27
11
3
2
91
27
11
5
7
104
33
11
5
2
104
33
12
5
8
117
31
12
5
2
115
31...

output:

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

result:

ok Accepted. 8885 queries used.

Test #7:

score: 0
Accepted
time: 11ms
memory: 7676kb

input:

1000
3
5
2
3
2
7
12
8
5
2
11
3
2
11
5
7
15
8
5
3
15
8
5
2
19
7
3
2
22
41
61
50
29
11
5
3
29
11
5
3
37
11
5
2
37
13
23
29
46
18
8
5
3
45
17
7
5
3
53
14
7
5
3
51
11
7
5
3
58
13
7
5
3
57
18
38
29
69
21
9
6
69
22
9
6
80
27
12
6
9
80
28
13
5
3
93
28
13
6
9
94
30
13
6
9
109
38
13
5
2
108
38
13
5
9
122
36
...

output:

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

result:

ok Accepted. 8815 queries used.

Test #8:

score: 0
Accepted
time: 17ms
memory: 7672kb

input:

1000
3
5
2
5
9
9
13
9
5
3
12
5
3
11
5
2
15
7
3
2
17
37
29
22
23
8
5
2
22
7
3
2
27
9
3
2
27
63
44
35
35
12
21
15
35
13
6
9
42
17
9
5
2
42
18
8
5
51
17
8
5
3
52
15
7
5
3
63
21
8
5
2
65
23
46
37
29
76
23
8
5
3
76
23
7
5
3
89
30
12
23
17
89
29
13
6
9
101
29
13
5
2
100
29
12
3
2
114
37
11
5
7
115
38
12
2...

output:

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

result:

ok Accepted. 8823 queries used.

Test #9:

score: 0
Accepted
time: 6ms
memory: 7636kb

input:

1000
3
6
5
2
8
5
8
5
2
13
24
18
13
5
2
18
9
13
18
8
5
3
23
7
5
3
23
9
17
30
13
5
2
29
12
3
2
35
9
3
2
32
5
3
2
37
6
4
3
2
33
6
4
3
2
43
11
24
33
42
15
24
33
51
21
9
6
51
22
9
5
2
61
21
9
17
13
63
23
8
5
2
75
29
11
3
2
80
30
11
5
7
93
29
11
5
2
95
26
12
5
8
107
35
71
53
44
110
37
13
5
3
125
37
13
5
2...

output:

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

result:

ok Accepted. 8815 queries used.

Test #10:

score: 0
Accepted
time: 5ms
memory: 7624kb

input:

1000
2
5
6
9
9
6
9
5
2
12
3
2
12
22
17
17
8
5
3
15
7
5
3
22
43
36
29
23
9
5
2
30
13
5
9
30
13
5
3
37
11
5
2
36
11
5
8
42
14
8
5
3
41
15
7
5
3
50
17
32
41
51
17
9
5
2
62
23
8
5
61
23
9
18
13
71
24
9
5
2
74
24
9
18
13
86
30
13
6
9
87
30
13
5
3
100
29
12
5
3
100
28
9
5
3
115
36
12
21
15
115
35
13
5
3
1...

output:

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

result:

ok Accepted. 8811 queries used.

Test #11:

score: 0
Accepted
time: 23ms
memory: 7544kb

input:

1000
2
5
5
2
8
5
9
18
13
6
9
13
5
2
18
8
5
18
9
13
23
9
5
3
24
8
5
2
30
13
24
18
30
13
5
3
37
11
5
2
36
11
3
2
44
17
29
22
45
17
9
12
55
17
9
5
3
55
17
7
5
3
64
21
7
5
3
64
21
9
15
75
21
9
6
76
23
9
5
2
88
30
13
5
8
88
31
13
24
18
102
31
13
5
2
102
31
13
5
9
116
38
13
5
2
116
38
12
5
8
131
37
12
5
2...

output:

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

result:

ok Accepted. 8804 queries used.

Extra Test:

score: 0
Extra Test Passed