QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456174 | #8819. CNOI Knowledge | 233L | AC ✓ | 344ms | 38592kb | C++14 | 3.1kb | 2024-06-27 12:22:26 | 2024-06-27 12:22:26 |
Judging History
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