QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566800#8469. Comedy’s Not Omnipotentucup-team1231WA 612ms8956kbC++232.4kb2024-09-16 01:48:212024-09-16 01:48:22

Judging History

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

  • [2024-09-16 01:48:22]
  • 评测
  • 测评结果:WA
  • 用时:612ms
  • 内存:8956kb
  • [2024-09-16 01:48:21]
  • 提交

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<=5) 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+=N)
        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: 612ms
memory: 8956kb

input:

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

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 14 15 16 17 18
? 5 19 20 21 22 23
? 5 14 19 24 25 26
? 5 15 16 20 24 25
? 5 15 17 21 24 26
? 5 16 17 22 25 26
? 4 16 17 20 24
? 5 27 28 29 30 31
? 5 32 33 34 35 36
? 5 27 32 37 38 39
? 5 28 29 33 37 38
? 5 30 ...

result:

wrong answer Too many queries: 50000