QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566794#8469. Comedy’s Not Omnipotentucup-team1231WA 1924ms6828kbC++232.4kb2024-09-16 01:45:292024-09-16 01:45:29

Judging History

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

  • [2024-09-16 01:45:29]
  • 评测
  • 测评结果:WA
  • 用时:1924ms
  • 内存:6828kb
  • [2024-09-16 01:45:29]
  • 提交

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 ss=1./s.size();
    // ld anss=8e18;
    if(s.size()<=2) {
        int w = s[0]^s[1];
        I = w&-w;
    }
    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);
        }
        ld H=0;
        for(int j=0;j<=N;++j) if(m[j]) {
            ld i = m[j]*ss;
            H -= i * log(i);
        }
        // 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[123333];
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<=6) iii.push_back(i);
    }
    auto S=EV(V,root);
    cerr<<S<<"++\n";
    int n;scanf("%d",&n);
    for(int i=0;i+N<n;++i)
        work(i);
    work(n-N);
    printf("= ");
    for(int i=0;i<n;++i) putchar(ans[i]+48);
    printf("\n");
    fflush(stdout);
}

详细

Test #1:

score: 0
Wrong Answer
time: 1924ms
memory: 6828kb

input:

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

output:

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

result:

wrong answer Too many queries: 637357