QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#456174#8819. CNOI Knowledge233LAC ✓344ms38592kbC++143.1kb2024-06-27 12:22:262024-06-27 12:22:26

Judging History

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

  • [2024-06-27 12:22:26]
  • 评测
  • 测评结果:AC
  • 用时:344ms
  • 内存:38592kb
  • [2024-06-27 12:22:26]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ldb long double
#define pii pair<int,int>
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define se second
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define all(_box) _box.begin(),_box.end()
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lbd lower_bound
#define ubd upper_bound
#define deb(x) cerr<<#x<<'='<<(x)<<' '
using namespace std;
namespace HH{//string hashing only
    int mod[3]={999999797,int(1e9+97),int(1e9+297)};
    struct H{
        int x,y,z;

        H(){x=y=z=0;}
        H(int val){x=y=z=val;}
        H(int x,int y,int z):x(x),y(y),z(z){}
        friend H operator+(const H &u,const H &v){
            return H(
                (u.x+v.x)%mod[0],
                (u.y+v.y)%mod[1],
                (u.z+v.z)%mod[2]
            );
        }
        friend H operator-(const H &u){
            return H(
                mod[0]-u.x,
                mod[1]-u.y,
                mod[2]-u.z
            );
        }
        friend H operator-(const H &u,const H &v){
            return u+(-v);
        }
        friend H operator*(const int &u,const H &v){
            return H(
                1ll*u*v.x%mod[0],
                1ll*u*v.y%mod[1],
                1ll*u*v.z%mod[2]
            );
        }
        friend H operator*(const H &u,const H &v){
            return H(
                1ll*u.x*v.x%mod[0],
                1ll*u.y*v.y%mod[1],
                1ll*u.z*v.z%mod[2]
            );
        }
        friend bool operator==(const H &u,const H &v){
            return u.x==v.x&&u.y==v.y&&u.z==v.z;
        }
        friend bool operator!=(const H &u,const H &v){
            return !(u==v);
        }
        friend bool operator<(const H &u,const H &v){
            if(u.x!=v.x)return u.x<v.x;
            if(u.y!=v.y)return u.y<v.y;
            return u.z<v.z;
        }
    };
}
using HH::H;

const int base=19937;
const int N=1e3+4;
int n,cnt;
int f[N][N];
int a[N];
H sum[N];
map<H,int>mp;

int query(int l,int r){
    cout<<"? "<<l<<' '<<r<<endl;
    int res;
    cin>>res;
    return res;
}
bool check(int l,int r){
    return query(l,r)==f[l][r-1]+r-l+1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x=0;
        for(int j=10;j>=0;j--){
            int y=x|(1<<j);
            if(y<i&&check(i-y,i))x=y;
        }
        if(i-x-1==0)a[i]=++cnt;
        else a[i]=a[i-x-1];
        
        sum[i]=base*sum[i-1]+H(a[i]);
        H pw(1);
        for(int j=i-1;j>=0;j--){
            pw=base*pw;
            H cur=sum[i]-sum[j]*pw;
            f[j][i]+=f[j+1][i];
            f[mp[cur]][i]--,mp[cur]=j+1;
        }
        for(int j=1;j<=i;j++)
            f[j][i]+=f[j][i-1]+i-j+1;
        
        // deb(i),cerr<<'\n';
        // for(int j=1;j<=i;j++)
        //     deb(j),deb(f[j][i]),cerr<<'\n';
    }
    cout<<"! ";
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
    cout<<endl;
}

详细

Test #1:

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

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: 301ms
memory: 38248kb

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: 303ms
memory: 38376kb

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: 310ms
memory: 38248kb

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: 344ms
memory: 38252kb

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: 276ms
memory: 38292kb

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: 331ms
memory: 38592kb

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: 313ms
memory: 38592kb

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: 295ms
memory: 38540kb

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: 303ms
memory: 38492kb

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: 318ms
memory: 38584kb

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