QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#488801 | #8819. CNOI Knowledge | czc | WA | 65ms | 22464kb | C++14 | 989b | 2024-07-24 15:26:28 | 2024-07-24 15:26:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
const ull p=131;
using namespace std;
int n;
inline int ask(int l,int r){
cout<<"? "<<l<<" "<<r<<endl;
int x; cin>>x;
return x;
}
unordered_map<ull,int> mp;
const int maxn=1e3+5;
int s[maxn],cnt[maxn],tot;
ull h[maxn],pw[maxn];
inline int get(int l,int r){
int ret=0;
for(int i=l;i<=r;i++) ret+=cnt[i];
return ret;
}
int main(){
cin>>n;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*p;
for(int i=1;i<=n;i++){
if(i==1 || get(1,i-1)+i==ask(1,i)){
s[i]=++tot;
}
else{
int l=2,r=i;
while(l<r){
int mid=(l+r)>>1;
if(ask(mid,i-1)+(i-mid+1)==ask(mid,i)) r=mid;
else l=mid+1;
}
s[i]=s[l-1];
}
h[i]=h[i-1]*p+(ull)s[i];
for(int j=1;j<=i;j++){
if(!mp[h[i]-h[j-1]*pw[i-j+1]]){
mp[h[i]-h[j-1]*pw[i-j+1]]=1;
cnt[j]++;
}
}
}
cout<<"! ";
for(int i=1;i<=n;i++) cout<<s[i]<<" ";
cout<<endl;
return 0;
}
/*
1 2 3 4 5 6 2 5 7 7 2 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3532kb
input:
12 3 6 10 15 21 27 6 10 10 15 15 20 34 6 9 1 3 3 6 43 52 10 14 3 5 1 2 62 14 19 2 5 5 8 72 13 19 33 40 19 25
output:
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ? 1 7 ? 4 6 ? 4 7 ? 3 6 ? 3 7 ? 2 6 ? 2 7 ? 1 8 ? 5 7 ? 5 8 ? 7 7 ? 7 8 ? 6 7 ? 6 8 ? 1 9 ? 1 10 ? 6 9 ? 6 10 ? 8 9 ? 8 10 ? 9 9 ? 9 10 ? 1 11 ? 6 10 ? 6 11 ? 9 10 ? 9 11 ? 8 10 ? 8 11 ? 1 12 ? 7 11 ? 7 12 ? 4 11 ? 4 12 ? 6 11 ? 6 12 ! 1 2 3 4 5 6 2 5 7 7 5 6
result:
ok Accepted. 41 queries used.
Test #2:
score: -100
Wrong Answer
time: 65ms
memory: 22464kb
input:
1000 3 5 1 2 7 1 2 11 2 5 3 7 16 3 5 1 2 21 5 7 1 2 27 3 7 11 16 7 11 34 7 11 3 5 1 3 41 8 11 3 5 1 2 48 11 15 2 3 1 2 57 11 14 2 3 1 2 66 14 17 3 4 1 2 75 11 13 3 4 1 2 84 13 15 3 4 1 2 96 7 15 39 47 23 31 15 23 108 15 23 7 11 3 5 1 3 124 20 27 8 11 3 5 1 3 140 27 36 7 11 3 5 1 2 156 31 39 8 11 2 3...
output:
? 1 2 ? 1 3 ? 2 2 ? 2 3 ? 1 4 ? 3 3 ? 3 4 ? 1 5 ? 3 4 ? 3 5 ? 2 4 ? 2 5 ? 1 6 ? 4 5 ? 4 6 ? 5 5 ? 5 6 ? 1 7 ? 4 6 ? 4 7 ? 6 6 ? 6 7 ? 1 8 ? 5 7 ? 5 8 ? 3 7 ? 3 8 ? 4 7 ? 4 8 ? 1 9 ? 5 8 ? 5 9 ? 7 8 ? 7 9 ? 8 8 ? 8 9 ? 1 10 ? 6 9 ? 6 10 ? 8 9 ? 8 10 ? 9 9 ? 9 10 ? 1 11 ? 6 10 ? 6 11 ? 9 10 ? 9 11 ? 1...
result:
wrong answer Too many queries.