QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#566759 | #8469. Comedy’s Not Omnipotent | ucup-team1231 | TL | 0ms | 0kb | C++23 | 2.3kb | 2024-09-16 01:33:15 | 2024-09-16 01:33:15 |
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) {
cout << "? " << v.size();
for (int z: v) cout << " " << z+1;
cout << endl;
int z;
cin >> 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);
if(i&&__builtin_popcount(i)<=6) iii.push_back(i);
}
auto S=EV(V,root);
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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
100000 3 5 6 3 1 4 6 2 2 2 1 4 5 5 5 5 1 0 4 5 4 5 4 2 1 5 5 4 4 1 0 5 4 4 6 3 1 6 4 3 3 1 0 6 4 2 1 1 5 4 5 6 2 0 5 4 5 5 3 2 0 5 4 5 4 4 2 4 5 4 4 4 1 4 4 4 6 1 1 0 4 4 4 3 4 6 1 4 5 4 4 4 2 0 4 4 4 4 1 1 4 3 4 5 3 3 0 5 3 5 2 2 4 4 5 5 1 0 4 4 4 4 4 3 0 5 4 4 4 4 5 1 4 5 4 6 0 0 3 6 3 3 2 3 5 5 3...
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 5 ? 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 7 ? 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 14 ? 6 4 5 6 7 8 9 ? 6 10 11 12 13 14 15 ? 6 ...