QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#684797 | #7161. Guessing Game | OccDreamer | 0 | 1ms | 3816kb | C++14 | 2.5kb | 2024-10-28 15:57:47 | 2024-10-28 15:57:47 |
answer
#include<bits/stdc++.h>
using namespace std;
const int B = 32;
const int MAXN = 1e5 + 5;
int a[MAXN];
int p, n, subsum[MAXN], dep[MAXN];
int sum, bel[MAXN], idx[MAXN], b[MAXN];
bool mark[MAXN];
pair<int,int> c[MAXN];
mt19937 rnd(time(0));
inline void build(int p, int l, int r){
subsum[p]=r-l+1;
if(l==r) return dep[p]=1, void();
int mid=(l+r)>>1;
build(p<<1,l,mid), build(p<<1|1,mid+1,r); dep[p]=dep[p<<1]+1;
return ;
}
inline int add(int p, int l, int r, int pos){
subsum[p]--; int res=0;
if(subsum[p]==0) res=dep[p];
if(l==r) return res;
int mid=(l+r)>>1;
if(pos<=mid) res=max(add(p<<1,l,mid,pos),res);
else res=max(add(p<<1|1,mid+1,r,pos),res);
return res;
}
inline void solve1(){
cout << 7 << endl; int sum=0;
for(int i=0;i<B;++i) bel[i]=i/2;
for(int i=1;i<=n-B;++i){
int x;
cin >> x; sum+=x, sum%=65536;
cout << 7 << endl; mark[x]=1, a[x]=7;
}
int tot=0;
for(int i=0;i<n;++i){
if(mark[i]) continue;
idx[i]=tot; b[tot]=i; ++tot;
}
build(1,0,B-1);
// cerr << "sum=" << sum << endl;
for(int i=1;i<=B;++i){
int x;
cin >> x;
int t=add(1,0,B-1,idx[x]);
// cerr << "t=" << t << endl;
if(t>1) cout << t+1 << endl, a[x]=t+1;
else{
if((sum>>bel[idx[x]])&1) t=2;
cout << t << endl, a[x]=t;
}
}
int x; cin >> x; a[x]=7;
return ;
}
inline void solve2(){
//for(int i=0;i<n;++i) cin >> a[i];
int tot7=0;
for(int i=0;i<n;++i) tot7+=a[i]==7;
if(n-tot7==B){
int tot=0;
for(int i=0;i<n;++i)
if(a[i]==7) continue;
else c[++tot]=make_pair(a[i],i);
int l=1, r=B, now=6;
while(l+1<r){
int mid=(l+r)>>1, L=-1, R=-1;
for(int i=l;i<=mid;++i) L=c[i].first==now?c[i].second:L;
for(int i=mid+1;i<=r;++i) R=c[i].first==now?c[i].second:R;
if(L==R){
cout << L << ' ' << R << endl;
return ;
}
if(L==-1) r=mid-1;
else l=mid+1; --now;
}
cout << c[l].second << ' ' << c[r].second << endl;
}
else{
int s=0, tot=0, ss=0;
for(int i=0;i<n;++i) s+=i, s%=65536;
for(int i=0;i<n;++i){
if(a[i]==7) continue;
(s+=65536-i%65536)%=65536;
if(a[i]==1) ++tot;
if(a[i]==2) ss|=1<<tot, ++tot;
}
ss%=65536;
// cerr << "sum=" << ss << endl;
(s+=65536-ss)%=65536;
// cerr << "lol" << endl;
if(s+(1<<16)>n) cout << s << ' ' << s << endl;
else cout << s << ' ' << s+(1<<16) << endl;
}
return ;
}
int main(){
freopen("guess.in","r",stdin);
// freopen("guess.out","w",stdout);
cin >> p >> n;
if(p==1) solve1();
else solve2();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3816kb
input:
output:
0 0
input:
output:
0 0
result:
wrong answer Token "WA" doesn't correspond to pattern "OK"