QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #340334 | #8216. Jumbled Primes | ucup-team191 | AC ✓ | 727ms | 3600kb | C++23 | 5.7kb | 2024-02-28 21:16:23 | 2024-02-28 21:16:24 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=300010,MOD=1e9+7;
const bool DEB=0;
const char en='\n';
const ll LLINF=1ll<<60;
int n=100,ar[N],cq;
int gg[N];
string cor;
int ask(int i,int j)
{
assert(i!=j);
++cq;
if (DEB) return gcd(ar[i],ar[j]);
cout<<"? "<<i+1<<' '<<j+1<<endl;
int x;
cin>>x;
return x;
}
bool comp(int x)
{
for (int i=2;i<x;++i) if (x%i==0) return 1;
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int z=0;z<1000;++z)
{
for (int i=0;i<n;++i) gg[i]=1;
if (DEB)
{
for (int i=0;i<n;++i) ar[i]=i+1;
random_shuffle(ar,ar+n);
cor.clear();
for (int i=0;i<n;++i) cor.pb('1'-comp(ar[i]));
}
bool f4=0,f5=0,f6=0,f7=0;
int x4=-1,y4=-1,g4=-1;
while (!f5 || !f6 || !f7)
{
int x=rand()%100,y=rand()%100;
if (x==y) continue;
int g=ask(x,y);
if (g%5==0 && !f5)
{
f5=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
for (int i=0;i<n;++i) if (i!=x && i!=y)
{
gg[i]=lcm(gg[i],ask(i,x));
}
}
if (g%6==0 && !f6)
{
f6=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
for (int i=0;i<n;++i) if (i!=x && i!=y)
{
gg[i]=lcm(gg[i],ask(i,x));
}
}
if (g%7==0 && !f7)
{
f7=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
for (int i=0;i<n;++i) if (i!=x && i!=y)
{
gg[i]=lcm(gg[i],ask(i,x));
}
}
if (g%4==0 && !f4)
{
f4=1;
g4=g;
x4=x;
y4=y;
}
}
vi s2;
bool i4=0;
for (int i=0;i<n;++i)
{
if (gg[i]==2) s2.pb(i);
if (gg[i]==4) i4=f4=1;
}
if (f4 && !i4)
{
gg[x4]=lcm(gg[x4],g4);
gg[y4]=lcm(gg[y4],g4);
}
while (!f4)
{
int x=s2[rand()%s2.size()];
int y=s2[rand()%s2.size()];
if (x==y) continue;
int g=ask(x,y);
if (g%4==0)
{
f4=1;
x4=x;
y4=y;
gg[x4]=lcm(gg[x4],g);
gg[y4]=lcm(gg[y4],g);
}
}
if (!i4)
{
for (auto i: s2) if (i!=x4 && i!=y4)
{
gg[i]=lcm(gg[i],ask(i,x4));
}
s2.clear();
for (int i=0;i<n;++i) if (gg[i]==2) s2.pb(i);
}
vi posp;
for (int i=0;i<n;++i) if (gg[i]==1)
{
posp.pb(i);
}
for (auto x: s2)
{
int mak=-1;
for (auto y: posp)
{
int g=ask(x,y);
if (g>1)
{
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
mak=y;
break;
}
}
vi novposp;
for (auto y: posp) if (y!=mak) novposp.pb(y);
posp=novposp;
}
//do 3
vi s3;
for (int i=0;i<n;++i) if (gg[i]==3) s3.pb(i);
bool i9=0;
for (int i=0;i<n;++i) if (gg[i]==9) i9=1;
if (!i9)
{
bool f9=0;
while (!f9)
{
int x=s3[rand()%s3.size()];
int y=s3[rand()%s3.size()];
if (x==y) continue;
int g=ask(x,y);
if (g%9==0)
{
f9=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
for (auto xx: s3) if (xx!=x && xx!=y) gg[xx]=lcm(gg[xx],ask(xx,x));
}
}
s3.clear();
for (int i=0;i<n;++i) if (gg[i]==3) s3.pb(i);
}
vi traz;
vi fou(100);
vi pri={11,13,17,19,23,29,31};
for (int i=0;i<n;++i)
{
for (auto x: pri) if (gg[i]%x==0 && !fou[x])
{
fou[x]=1;
traz.pb(i);
}
}
fou=vi(100);
for (auto x: s3)
{
for (auto y: traz) if (!fou[y])
{
int g=ask(x,y);
if (g/gcd(g,210*210*2*2*3)>1)
{
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
fou[y]=1;
break;
}
}
}
//for (auto x: s3) cout<<gg[x]<<' ';
//cout<<en;
vi s5;
for (int i=0;i<n;++i) if (gg[i]==5) s5.pb(i);
vi kand25;
for (int i=0;i<n;++i) if (gg[i]%15==0) kand25.pb(i);
bool f25=0;
for (auto x: s5) for (auto y: kand25) if (!f25)
{
int g=ask(x,y);
if (g%25==0)
{
f25=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
break;
}
}
fou=vi(100);
traz.clear();
pri={11,13,17,19};
for (int i=0;i<n;++i)
{
for (auto x: pri) if (gg[i]%x==0 && !fou[x])
{
fou[x]=1;
traz.pb(i);
}
}
fou=vi(100);
for (auto x: s5)
{
for (auto y: traz) if (!fou[y])
{
int g=ask(x,y);
if (g/gcd(g,210*210*2*2*3)>1)
{
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
fou[y]=1;
break;
}
}
}
vi s7;
for (int i=0;i<n;++i) if (gg[i]==7) s7.pb(i);
fou=vi(100);
traz.clear();
pri={11,13};
for (int i=0;i<n;++i)
{
for (auto x: pri) if (gg[i]%x==0 && !fou[x])
{
fou[x]=1;
traz.pb(i);
}
}
fou=vi(100);
for (auto x: s7)
{
for (auto y: traz) if (!fou[y])
{
int g=ask(x,y);
if (g/gcd(g,210*210*2*2*3)>1)
{
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
fou[y]=1;
break;
}
}
}
vi kand49;
for (int i=0;i<n;++i) if (gg[i]==14 || gg[i]==98) kand49.pb(i);
bool f49=0;
for (auto x: s7) for (auto y: kand49) if (!f49)
{
int g=ask(x,y);
if (g%49==0)
{
f49=1;
gg[x]=lcm(gg[x],g);
gg[y]=lcm(gg[y],g);
break;
}
}
string s;
for (int i=0;i<n;++i) if (gcd(gg[i],210)==1) s.pb('1');
else s.pb('0');
for (auto x: s2) if (gg[x]==2) s[x]='1';
for (auto x: s3) if (gg[x]==3) s[x]='1';
for (auto x: s5) if (gg[x]==5) s[x]='1';
for (auto x: s7) if (gg[x]==7) s[x]='1';
/*if (s!=cor)
{
cout<<"WRONG"<<endl;
cout<<s<<endl;
cout<<cor<<endl;
cout<<s.size()<<' '<<cor.size()<<en;
cout<<i4<<endl;
for (int i=0;i<n;++i) if (s[i]!=cor[i]) cout<<i<<' '<<s[i]<<' '<<cor[i]<<' '<<gg[i]<<' '<<ar[i]<<en;
exit(0);
}
else cout<<"CORRECT"<<endl;*/
cout<<"! "<<s<<endl;
}
//cout<<cq<<endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 727ms
memory: 3600kb
input:
1 1 1 3 1 1 1 3 1 2 1 1 3 1 1 1 1 1 2 4 1 1 6 3 7 1 1 3 2 2 1 1 1 2 2 6 3 14 1 6 2 2 2 6 3 1 3 2 6 3 1 1 1 3 1 3 1 2 21 2 2 1 1 1 2 2 2 1 6 6 2 1 7 1 6 21 7 3 2 14 2 1 2 3 1 6 6 14 3 1 3 14 14 2 2 2 2 1 2 7 1 1 6 3 6 1 2 3 2 6 2 3 1 6 2 1 2 7 1 42 2 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 ...
output:
? 84 87 ? 78 16 ? 94 36 ? 87 93 ? 50 22 ? 63 28 ? 91 60 ? 64 27 ? 41 27 ? 73 37 ? 12 69 ? 68 30 ? 83 31 ? 63 24 ? 68 36 ? 30 3 ? 23 59 ? 70 68 ? 94 57 ? 12 43 ? 30 74 ? 22 20 ? 85 38 ? 1 85 ? 2 85 ? 3 85 ? 4 85 ? 5 85 ? 6 85 ? 7 85 ? 8 85 ? 9 85 ? 10 85 ? 11 85 ? 12 85 ? 13 85 ? 14 85 ? 15 85 ? 16 8...
result:
ok Primes are found successfully with S = 561198 queries total