QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471184 | #8216. Jumbled Primes | PhantomThreshold | AC ✓ | 766ms | 3912kb | C++17 | 5.5kb | 2024-07-10 19:08:12 | 2024-07-10 19:08:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int __CNT=0;
int __totCNT=0;
//#define DEBUG
#ifdef DEBUG
int ha[105];
#endif
#ifdef DEBUG
mt19937 rng_ha((unsigned long long)(new char));
void prepare_ha(){
for (int i=1;i<=100;i++) ha[i]=i;
shuffle(ha+1,ha+100+1,rng_ha);
}
#endif
int real_ask(int i,int j){
__CNT++;
cout << "? " << i << " " << j << endl;
int ret=0;
#ifdef DEBUG
ret=__gcd(ha[i],ha[j]);
#else
cin >> ret;
#endif
return ret;
}
int rec[105][105];
int disc[105];
int notp[105];
void upd(int i,int g){
int _gg=__gcd(disc[i],g);
disc[i]=disc[i]*g/_gg;
}
int ask(int i,int j){
assert(i!=j);
if (i>j) swap(i,j);
if (rec[i][j]!=0) return rec[i][j];
rec[i][j]=real_ask(i,j);
upd(i,rec[i][j]);
upd(j,rec[i][j]);
return rec[i][j];
}
void answer(const vector<int> &ans){
cout << "! ";
for (int i=1;i<=100;i++) cout << ans[i];
cout << endl;
#ifdef DEBUG
for (int i=1;i<=100;i++) assert(notp[ha[i]]!=ans[i]);
#endif
}
//mt19937 rng((unsigned long long)(new char));
mt19937 rng(58);
pair<vector<int>,vector<int>> fliter(const vector<int> &v,int k,int qingding=0){
int pos=qingding;
int sz=v.size();
while (!pos){
for (int i=1;i<=100;i++) if (disc[i]%k==0){pos=i;break;}
if (pos!=0) break;
int x=rng()%sz;
int y=rng()%sz;
while (y==x) y=rng()%sz;
ask(v[x],v[y]);
}
// cerr << "pos,disc[pos],ha[pos] : " << pos << " " << disc[pos] << " " << ha[pos] << endl;
vector<int> vk;
vector<int> vnotk;
for (auto x:v){
int tmp=0;
if (x!=pos) tmp=ask(x,pos);
else tmp=disc[x];
if (tmp%k==0) vk.push_back(x);
else vnotk.push_back(x);
}
return make_pair(vk,vnotk);
}
void solve(){
vector<int> ans(105);
for (int i=1;i<=100;i++){
for (int j=1;j<=100;j++){
rec[i][j]=0;
}
}
for (int i=1;i<=100;i++) disc[i]=1;
vector<int> v;
for (int i=1;i<=100;i++) v.push_back(i);
int pos6=0;
int pos5=0;
int pos7=0;
{
while (1){
for (int i=1;i<=100;i++){
if (disc[i]%6==0){
pos6=i;
}
if (disc[i]%5==0){
pos5=i;
}
if (disc[i]%7==0){
pos7=i;
}
}
if (pos6!=0 && pos5!=0 && pos7!=0) break;
int x=rng()%100;
int y=rng()%100;
while (y==x) y=rng()%100;
ask(v[x],v[y]);
}
}
auto [v2,vnot2]=fliter(v,2,pos6);
auto [v4,v2not4]=fliter(v2,4);
#ifdef DEBUG
cerr << "stage 1 : " << __CNT << endl;
#endif
vector<int> v3,vnot23;
for (auto x:vnot2){
if (disc[x]%3==0) v3.push_back(x);
else vnot23.push_back(x);
}
auto [v5,vnot235]=fliter(vnot23,5,pos5);
auto [v7,vnot2357]=fliter(vnot235,7,pos7);
#ifdef DEBUG
cerr << "stage 2 : " << __CNT << endl;
#endif
vector<int> v2rest=v2not4;
{
{
auto [_1,_2]=fliter(v2rest,3,pos6);
swap(_2,v2rest);
}
{
auto [_1,_2]=fliter(v2rest,5,pos5);
swap(_2,v2rest);
}
{
auto [_1,_2]=fliter(v2rest,7,pos7);
swap(_2,v2rest);
}
}
#ifdef DEBUG
cerr << "stage 3 : " << __CNT << endl;
#endif
vector<int> v3rest=v3;
{
{
auto [_1,_2]=fliter(v3rest,9);
swap(_2,v3rest);
}
{
auto [_1,_2]=fliter(v3rest,5,pos5);
swap(_2,v3rest);
}
{
auto [_1,_2]=fliter(v3rest,7,pos7);
swap(_2,v3rest);
}
}
#ifdef DEBUG
cerr << "stage 4 : " << __CNT << endl;
#endif
vector<int> v5rest=v5;
{
{
auto [_1,_2]=fliter(v5rest,7,pos7);
swap(_2,v5rest);
}
}
#ifdef DEBUG
cerr << "stage 5 : " << __CNT << endl;
#endif
{
vector<int> vis(105);
for (auto x:v2rest){
if (vis[x]) continue;
for (auto y:v3rest){
if (vis[y]) continue;
if (x!=y){
int tmp=ask(x,y);
if (tmp!=1){
vis[x]=1;
vis[y]=1;
break;
}
}
}
}
}
#ifdef DEBUG
cerr << "stage 6 : " << __CNT << endl;
#endif
for (auto x:v3rest){
for (auto y:v5rest){
if (x!=y) ask(x,y);
}
}
#ifdef DEBUG
cerr << "stage 7 : " << __CNT << endl;
#endif
for (auto x:v5rest){
for (auto y:v7){
if (x!=y) ask(x,y);
}
}
#ifdef DEBUG
cerr << "stage 8 : " << __CNT << endl;
#endif
{
vector<int> v35;
for (int i=1;i<=100;i++) if (disc[i]%15==0) v35.push_back(i);
vector<int> v5only;
for (int i=1;i<=100;i++) if (disc[i]==5) v5only.push_back(i);
for (auto x:v5only){
for (auto y:v35){
if (x!=y) ask(x,y);
}
}
}
#ifdef DEBUG
cerr << "stage 9 : " << __CNT << endl;
#endif
{
vector<int> v27;
for (int i=1;i<=100;i++) if (disc[i]%14==0) v27.push_back(i);
vector<int> v7only;
for (int i=1;i<=100;i++) if (disc[i]==7) v7only.push_back(i);
for (auto x:v7only){
for (auto y:v27){
if (x!=y) ask(x,y);
}
}
}
#ifdef DEBUG
cerr << "stage 10 : " << __CNT << endl;
#endif
{
vector<int> v2only;
for (int i=1;i<=100;i++) if (disc[i]==2) v2only.push_back(i);
for (auto x:v2only){
for (auto y:vnot2357){
if (x!=y) ask(x,y);
}
}
}
#ifdef DEBUG
cerr << "stage 11 : " << __CNT << endl;
#endif
for (int i=1;i<=100;i++) if (disc[i]==1 || !notp[disc[i]]) ans[i]=1;
answer(ans);
return;
}
int main(){
ios_base::sync_with_stdio(false);
notp[1]=0;
for (int i=2;i<=100;i++){
for (int j=i+i;j<=100;j+=i) notp[j]=1;
}
int Tcase=1000;
for (int ttt=1;ttt<=Tcase;ttt++){
#ifdef DEBUG
prepare_ha();
#endif
__CNT=0;
solve();
__totCNT+=__CNT;
cerr << "turn , cnt , totcnt: " << ttt << " " << __CNT << " " << __totCNT << endl;
// assert(__totCNT<=1000*600);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 766ms
memory: 3912kb
input:
1 9 1 1 26 1 2 1 1 1 1 3 2 3 1 2 1 1 1 2 1 1 4 1 1 1 1 2 1 1 1 1 6 4 8 1 1 6 3 1 1 3 2 1 2 2 2 1 1 1 1 1 1 1 7 3 1 1 5 3 1 1 1 3 2 2 1 1 1 2 16 3 2 1 12 4 4 16 12 3 1 3 2 24 3 1 1 1 3 1 3 1 8 3 2 24 2 1 1 1 4 16 2 1 6 6 4 1 1 1 6 3 1 3 2 2 4 1 4 3 1 12 4 3 1 3 2 8 2 2 16 8 1 2 1 1 1 6 3 48 1 6 4 3 2...
output:
? 16 73 ? 48 54 ? 50 59 ? 61 76 ? 6 86 ? 3 82 ? 25 47 ? 41 85 ? 59 67 ? 41 95 ? 9 100 ? 36 83 ? 13 25 ? 38 69 ? 15 98 ? 15 18 ? 64 97 ? 36 37 ? 3 62 ? 11 44 ? 5 11 ? 28 59 ? 20 65 ? 16 78 ? 12 16 ? 59 79 ? 8 40 ? 58 94 ? 70 79 ? 1 19 ? 20 54 ? 47 50 ? 38 53 ? 49 75 ? 64 90 ? 18 30 ? 25 68 ? 13 64 ? ...
result:
ok Primes are found successfully with S = 567810 queries total