QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#414473#8216. Jumbled Primesucup-team1231#AC ✓917ms3656kbC++203.5kb2024-05-19 02:10:382024-05-19 02:10:39

Judging History

你现在查看的是最新测评结果

  • [2024-05-19 02:10:39]
  • 评测
  • 测评结果:AC
  • 用时:917ms
  • 内存:3656kb
  • [2024-05-19 02:10:38]
  • 提交

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