QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414473 | #8216. Jumbled Primes | ucup-team1231# | AC ✓ | 917ms | 3656kb | C++20 | 3.5kb | 2024-05-19 02:10:38 | 2024-05-19 02:10:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
int N,cnt=0;
int p[10005];
int qry0(int a,int b) {
++cnt;
assert(a!=b&&a>=1&&a<=N&&b>=1&&b<=N);
#ifdef LOCAL
return __gcd(p[a],p[b]);
#else
cout<<"? "<<a<<" "<<b<<endl;
int x; cin>>x; return x;
#endif
}
map<int,int> MEM;
int qry(int a,int b) {
if(a>b) swap(a,b);
int&R=MEM[a*1000+b];
if(R) return R;
return R=qry0(a,b);
}
bool good(int x) {
for(int i=2;i*i<=x;++i) if(x%i==0) return 0;
return 1;
}
int kf[10009],ans[10009];
map<int,int> rr;
void report(int* rst) {
for(int i=1;i<=N;++i) {
assert(rst[i]>=0&&rst[i]<=1);
#ifdef LOCAL
//cout<<rst[i]<<","<<good(p[i])<<"|"<<p[i]<<"\n";
assert(rst[i]==good(p[i]));
#endif
}
#ifndef LOCAL
cout<<"! ";
for(int i=1;i<=N;++i)
cout<<rst[i];
cout<<endl;
#endif
}
void solve() {
MEM.clear();
//cout<<"wtf"<<endl;
for(int i=1;i<=N;++i) p[i]=i;
static mt19937_64 rng(123);
shuffle(p+1,p+1+N,rng);
rr.clear();
for(int i=1;i<=N;++i) kf[i]=ans[i]=0;
while(1) {
int x=rand()%N+1,y=rand()%N+1;
if(x==y) continue;
int u=qry(x,y);
if(u%6==0) rr[-6]=x;
if(u%7==0) rr[7]=x;
if(u%5==0) rr[5]=x;
if(rr.size()==3) break;
}
// cerr<<"haha\n";
for(int i=1;i<=N;++i) {
kf[i]=0;
int p=1;
for(auto g:rr) {
if(i==g.second) p*=abs(g.first);
else p*=qry(g.second,i);
for(int u:{2,3,5,7}) if(p%u==0) kf[i]|=1<<u;
if(__builtin_popcount(kf[i])>=3) break;
if(__builtin_popcount(kf[i])>=2&&(kf[i]&(1<<5))) break;
}
if((kf[i]&(1<<5))&&(kf[i]&(1<<7))) {
rr.erase(5);
rr.erase(7);
rr[35]=i;
}
}
// cerr<<"haha"<<__LINE__<<"\n";
map<int,vector<int>> pp;
map<int,int> bigp;
for(int i=1;i<=N;++i) {
if(kf[i]==0) ans[i]=1,bigp[i]=0;
pp[kf[i]].push_back(i);
}
// cerr<<"haha"<<__LINE__<<"\n";
vector<int> wx;
for(int u:{2,3,5,7}) {
auto V=pp[1<<u];
auto T=V;
{
int need=0;
if(u==5) need=(1<<5)|(1<<3);
if(u==7) need=(1<<2)|(1<<7);
if(u==2) need=(1<<2)|(1<<3)|(1<<7);
if(u==3) need=(1<<3)|(1<<7);
T.clear();
for(int i=1;i<=N;++i) if(kf[i]==need) T.push_back(i);
assert(T.size());
}
set<int> found;
for(auto x:V) {
bool ez=0;
for(auto y:T) if(x!=y&&qry(x,y)!=u) {
ez=1; break;
}
if(ez) continue;
for(auto&g:bigp) {
if(g.second*u>100) continue;
if(found.count(g.second)) continue;
int q=qry(g.first,x);
if(q==1) continue;
found.insert(g.second=q);
ez=1; break;
}
if(!ez) {
wx.push_back(x);
break;
}
}
}
for(auto s:wx) ans[s]=1;
// cout<<wx.size()<<"\n";
// for(auto g:wx) cout<<g<<" ";
// cout<<"\n";
// for(auto g:wx) cout<<p[g]<<" ";
// cout<<"\n";
// cerr<<"haha"<<__LINE__<<"\n";
// cout<<cnt<<"+\n";
report(ans);
}
int main() {
N=10*10;
for(int i=1;i<=1000;++i) {
solve();
}
#ifdef LOCAL
cout<<cnt<<"\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 917ms
memory: 3656kb
input:
1 1 1 3 1 1 1 3 1 2 1 1 3 1 1 1 1 1 2 4 1 1 6 2 1 3 1 2 1 1 2 1 2 1 1 2 1 1 4 1 1 1 6 1 1 1 1 5 3 1 4 1 1 1 2 2 1 1 4 2 1 5 19 1 1 1 1 1 5 2 1 1 1 1 1 1 1 17 1 3 1 1 1 1 2 2 1 1 1 1 1 1 1 4 1 1 16 1 1 16 1 1 1 1 2 1 2 1 1 2 5 1 1 2 4 1 3 4 1 2 3 1 2 1 3 1 2 1 1 1 4 2 1 1 2 5 1 5 3 1 4 1 1 1 3 5 3 1 ...
output:
? 84 87 ? 16 78 ? 36 94 ? 87 93 ? 22 50 ? 28 63 ? 60 91 ? 27 64 ? 27 41 ? 37 73 ? 12 69 ? 30 68 ? 31 83 ? 24 63 ? 36 68 ? 3 30 ? 23 59 ? 68 70 ? 57 94 ? 12 43 ? 30 74 ? 20 22 ? 38 85 ? 25 99 ? 16 71 ? 14 27 ? 81 92 ? 57 74 ? 63 71 ? 82 97 ? 6 26 ? 28 85 ? 6 37 ? 30 47 ? 14 58 ? 25 96 ? 46 83 ? 15 68...
result:
ok Primes are found successfully with S = 524464 queries total