QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#566794 | #8469. Comedy’s Not Omnipotent | ucup-team1231 | WA | 1924ms | 6828kb | C++23 | 2.4kb | 2024-09-16 01:45:29 | 2024-09-16 01:45:29 |
Judging History
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);
}
Details
Tip: Click on the bar to expand more detailed information
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