QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558800#9188. Light Bulbsthomaswmy0 1ms4284kbC++143.7kb2024-09-11 18:36:112024-09-11 18:36:12

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 18:36:12]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4284kb
  • [2024-09-11 18:36:11]
  • 提交

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;
}

詳細信息

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%