QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566767#8469. Comedy’s Not Omnipotentucup-team1231TL 0ms0kbC++232.4kb2024-09-16 01:37:012024-09-16 01:37:02

Judging History

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

  • [2024-09-16 01:37:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-16 01:37:01]
  • 提交

answer

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math")
#include <bits/stdc++.h>
using namespace std;

double H(const vector<double>& p) {
    double ret = 0;
    for(auto i : p) if(i) ret -= i * log(i);
    return ret / log(2);
}

int N=6;
typedef double ld;
// map<vector<int>,ld> G;
vector<int> iii;
const int S=2000000;
int go[S][15];
int mask[S],an=0;
double EV(const vector<int>& s,int& cur) {
    cur=++an;
    if(s.size()<=1) {
        mask[cur]=0;
        go[cur][0]=s[0];
        return 0;
    }
    // if(G.count(s)) return G[s];
    ld maxH=-100000; int I=-1;
    // ld anss=8e18;
    if(s.size()<=2) {
        for(int u=0;u<N;++u)
            if((s[0]^s[1])&(1<<u)) I=1<<u;
    }
    else for(auto i:iii) {
        int m[15];
        memset(m,0,sizeof m);
        for(auto p:s) {
            m[__builtin_popcount(p&i)]++;//.push_back(p);
        }
        vector<double> ss;
        for(int j=0;j<=N;++j) if(m[j]) ss.push_back(m[j]*1./s.size());
        auto h=H(ss);
        if(maxH<h) {
            maxH=h;
            I=i;
        }
    }
    int i=I;
    // cerr<<i<<" "<<maxH<<"?\n";
    map<int,vector<int>> m;
    for(auto p:s) {
        m[__builtin_popcount(p&i)].push_back(p);
    }
    mask[cur]=i;
    ld ans=1;
    for(auto t:m)
        ans+=EV(t.second,go[cur][t.first])*t.second.size()*1./s.size();
    return ans;
    // cerr<<anss<<"vs"<<ans<<"\n";
    // return G[s]=ans;//min(ans,anss);
}
int root;
int query(vector<int> v) {
    printf("? %d",int(v.size()));
    for (int z: v) printf(" %d",z+1);
    printf("\n");
    fflush(stdout);
    int z;
    scanf("%d",&z);
    return z;
}
int ans[1233];
void work(int l) {
    int w=root;
    while(mask[w]) {
        int q=mask[w];
        vector<int> ans;
        for(int u=0;u<N;++u) if(q&(1<<u)) ans.push_back(l+u);
        int o=query(ans);
        w = go[w][o];
    }
    int q=go[w][0];
    for(int u=0;u<N;++u) if(q&(1<<u)) ans[l+u]=1;
}
int main() {
    N=13;
    vector<int> V;
    for(int i=0;i<(1<<N);++i) {
        V.push_back(i);
        int pc=__builtin_popcount(i);
        if(i&&pc<=5) iii.push_back(i);
    }
    auto S=EV(V,root);
    // cerr<<S<<"++\n";
    int n;
    cin>>n;
    for(int i=0;i+N<n;++i)
        work(i);
    work(n-N);
    printf("= ");
    for(int i=0;i<n;++i) printf("%d",ans[i]);
    printf("\n");
    fflush(stdout);
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

100000
3
4
3
5
3
0
3
5
4
3
1
1
3
5
3
3
3
1
3
5
3
3
0
4
4
4
4
5
1
0
4
4
3
4
5
1
5
4
4
2
0
5
3
3
4
2
0
5
3
3
3
2
2
0
4
4
4
3
3
1
4
3
5
3
2
0
4
3
3
5
1
1
3
4
4
3
3
4
2
3
4
3
3
3
4
1
4
3
3
5
2
2
3
4
3
3
3
2
2
0
3
4
2
3
2
0
4
3
4
3
2
3
1
4
2
4
4
3
3
0
3
3
4
4
4
4
1
4
3
5
2
2
1
1
4
3
4
4
4
1
3
4
4
4
4
1
0...

output:

? 5 1 2 3 4 5
? 5 6 7 8 9 10
? 5 1 6 11 12 13
? 5 2 3 7 11 12
? 5 1 4 8 9 13
? 3 1 4 6
? 5 2 3 4 5 6
? 5 7 8 9 10 11
? 5 2 3 12 13 14
? 5 4 5 12 13 14
? 2 4 12
? 2 4 13
? 5 3 4 5 6 7
? 5 8 9 10 11 12
? 5 3 4 13 14 15
? 5 5 6 7 13 14
? 3 3 5 13
? 1 7
? 5 4 5 6 7 8
? 5 9 10 11 12 13
? 5 4 5 14 15 16
?...

result: