QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558800 | #9188. Light Bulbs | thomaswmy | 0 | 1ms | 4284kb | C++14 | 3.7kb | 2024-09-11 18:36:11 | 2024-09-11 18:36:12 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N=210;
const int B=1000;
const int BB=50;
mt19937 rnd(time(0));
typedef long long ll;
int n;
void print(vector<pair<int,int> > arr) {
static int a[N][N];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=0;
for(auto i:arr) a[i.first][i.second]=1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) printf("%d",a[i][j]);
printf("\n");
}
}
int query(vector<pair<int,int> > arr) {
printf("?\n");
print(arr);
fflush(stdout);
int val;
scanf("%d",&val);
return val;
}
void retans(vector<pair<int,int> > arr) {
printf("!\n");
print(arr);
fflush(stdout);
exit(0);
}
vector<int> X,Y;
vector<pair<int,int> > rx,ry;
int sz;
vector<pair<int,int> > ps;
vector<bitset<N> > sta;
void ins(int x,int y,bool isx) {
if(isx && count(X.begin(),X.end(),x)) {
rx.push_back({x,y});
X.erase(find(X.begin(),X.end(),x));
}
else if(count(Y.begin(),Y.end(),y)) {
ry.push_back({x,y});
Y.erase(find(Y.begin(),Y.end(),y));
}
if(!X.size()) retans(rx);
if(!Y.size()) retans(ry);
}
void upd() {
for(int i=0;i<sz;i++) {
int cnt0=0,cnt1=0;
for(auto j:sta) {
if(j[i]) cnt1++;
else cnt0++;
}
if(!cnt0) ins(ps[i].first,ps[i].second,1);
if(!cnt1) ins(ps[i].first,ps[i].second,0);
if(!cnt0 || !cnt1) {
vector<bitset<N> > arr;
for(auto &j:sta) for(int k=i;k<sz;k++) j[k]=j[k+1];
ps.erase(ps.begin()+i);
i--,sz--;
unordered_set<bitset<N> > st(sta.begin(),sta.end());
sta=vector<bitset<N> > (st.begin(),st.end());
}
}
}
void insp() {
while(sta.size()<B && sz<X.size()+Y.size()) {
shuffle(X.begin(),X.end(),rnd);
shuffle(Y.begin(),Y.end(),rnd);
if(count(ps.begin(),ps.end(),make_pair(X[0],Y[0]))) break;
ps.push_back({X[0],Y[0]});
vector<bitset<N> > ss;
for(auto i:sta) {
i[sz]=0;
ss.push_back(i);
i[sz]=1;
ss.push_back(i);
}
swap(ss,sta);
sz++;
}
}
int calc(bitset<N> ss,bitset<N> vis,bool usx) {
static bool vsx[N],vsy[N];
memset(vsx,0,sizeof(vsx)),memset(vsy,0,sizeof(vsy));
for(int i=0;i<sz;i++) {
if(vis[i]) {
if(ss[i]) vsx[ps[i].first]=1;
else vsy[ps[i].second]=1;
}
}
if(usx) for(auto i:rx) vsx[i.first]=1;
else for(auto i:ry) vsy[i.second]=1;
int cx=0,cy=0;
for(int i=1;i<=n;i++) cx+=vsx[i],cy+=vsy[i];
return (cx+cy)*n-cx*cy;
}
int cnt[N*N];
void ask() {
int mn=1e9;
bitset<N> mnmask=0;
bool mnux=0;
vector<int> pp;
for(int i=0;i<=100;i+=10) pp.push_back(i);
while(pp.size()<BB) pp.push_back(rnd()%30+60);
for(int p:pp) {
bitset<N> mask=0;
for(int i=0;i<sz;i++) mask[i]=rnd()%100<=p;
bool ux=rnd()&1;
memset(cnt,0,sizeof(cnt));
for(auto i:sta) cnt[calc(i,mask,ux)]++;
int mx=0;
for(int i=0;i<=n*n;i++) mx=max(mx,cnt[i]);
if(mx<mn) {
mn=mx,mnmask=mask,mnux=ux;
}
}
vector<pair<int,int> > arr;
if(mnux) arr=rx;
else arr=ry;
for(int i=0;i<sz;i++) if(mnmask[i]) arr.push_back(ps[i]);
int cc=query(arr);
vector<bitset<N> > ss;
for(auto i:sta) {
if(calc(i,mnmask,mnux)==cc) ss.push_back(i);
}
swap(ss,sta);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) X.push_back(i),Y.push_back(i);
sta={0};
while(true) {
upd();
insp();
ask();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 0ms
memory: 4116kb
input:
3 6 6
output:
? 000 111 110 ? 001 110 000 ! 001 001 010
result:
points 1.0 points 1.0 correct, 2 queries
Test #2:
score: 11
Accepted
time: 0ms
memory: 4032kb
input:
3 9 9
output:
? 000 111 110 ? 000 001 110 ! 000 001 110
result:
points 1.0 points 1.0 correct, 2 queries
Test #3:
score: 11
Accepted
time: 1ms
memory: 4032kb
input:
3 7 3 8 6 9
output:
? 000 111 110 ? 000 010 010 ? 100 100 110 ? 000 001 100 ? 001 001 100 ! 001 001 100
result:
points 1.0 points 1.0 correct, 5 queries
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 4284kb
input:
3 8 6 7 7
output:
? 000 111 110 ? 000 010 010 ? 010 010 010 ? 010 101 000 ! 010 101 000
result:
wrong answer wa: does not cover enough
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%