QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566767 | #8469. Comedy’s Not Omnipotent | ucup-team1231 | TL | 0ms | 0kb | C++23 | 2.4kb | 2024-09-16 01:37:01 | 2024-09-16 01:37:02 |
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 ?...