QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566800 | #8469. Comedy’s Not Omnipotent | ucup-team1231 | WA | 612ms | 8956kb | C++23 | 2.4kb | 2024-09-16 01:48:21 | 2024-09-16 01:48:22 |
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<=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