Submission #1353724

#TimeUsernameProblemLanguageResultExecution timeMemory
1353724Francisco_MartinLight Bulbs (EGOI24_lightbulbs)C++20
100 / 100
602 ms836 KiB
//EGOI 2024 Light Bulbs
//https://qoj.ac/contest/1765/problem/9188

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll MAXN = 205;
const ll MAXN2 = 1005;
mt19937 rng(0x50F14);

ll query(vvll &A,ll n){
    cout << "?" << endl; ll res;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) cout << A[i][j];
        cout << endl;
    }
    cin >> res; return res;
}
void ans(vvll &A,ll n){
    cout << "!" << endl;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) cout << A[i][j];
        cout << endl;
    }
    exit(0);
}

int main(){
    ll n, k=0;
    cin >> n;
    vvll H(n,vll(n,0)), V(n,vll(n,0)); vector<pair<ll,ll>> cand;
    vll rows, cols, R(n,0), C(n,0); ; vector<bitset<MAXN>> can(1,0);
    for(int i=0; i<n; i++) rows.push_back(i), cols.push_back(i);
    auto solve=[&](bitset<MAXN> &a,bitset<MAXN> &mask,bool flag){
        vll R2(n,0), C2(n,0); ll x=0, y=0;
        if(flag) R2=R;
        else C2=C;
        for(int i=0; i<k; i++) if(mask[i]){
            if(a[i]) R2[cand[i].first]=1;
            else C2[cand[i].second]=1;
        }
        for(int i=0; i<n; i++) x+=R2[i], y+=C2[i];
        return n*(x+y)-x*y;
    };
    while(true){
        for(int i=0; i<k; i++){
            ll cnt[2]={0,0}; auto [x,y]=cand[i];
            for(auto &a:can) cnt[a[i]]++;
            if(cnt[1]==0){
                for(int j=0; j<(ll)cols.size(); j++) if(cols[j]==y){
                    V[x][y]=1; C[y]++; cols.erase(cols.begin()+j); break;
                }
            }else if(cnt[0]==0){
                for(int j=0; j<(ll)rows.size(); j++) if(rows[j]==x){
                    H[x][y]=1; R[x]++; rows.erase(rows.begin()+j); break;
                }
            }
            if(rows.empty()) ans(H,n);
            if(cols.empty()) ans(V,n);
            if(cnt[0]==0 || cnt[1]==0){
                cand.erase(cand.begin()+i);
                for(auto &a:can) for(int j=i; j<k; j++) a[j]=a[j+1];
                k--; i--; can.erase(unique(can.begin(),can.end()),can.end());
            }
        }
        while((ll)can.size()<MAXN2 && k<(ll)rows.size()+(ll)cols.size()){
            shuffle(rows.begin(),rows.end(),rng); shuffle(cols.begin(),cols.end(),rng);
            if(count(cand.begin(),cand.end(),pair<ll,ll>{rows[0],cols[0]})) break;
            cand.push_back({rows[0],cols[0]}); vector<bitset<MAXN>> nCan;
            for(auto a:can) a[k]=0, nCan.push_back(a), a[k]=1, nCan.push_back(a);
            swap(can,nCan); k++; 
        }
        ll bst=1e18; bool bstFlag; bitset<MAXN> bstMask; vll prob={100,90,80,70,60,40,30,20,10};
        for(int i=0; i<50; i++) prob.push_back(rng()%70+20);
        for(auto p:prob){
            bitset<MAXN> mask; bool flag=((ll)(rng()%2)==1); map<ll,ll> freq; ll maxi=0;
            for(int i=0; i<k; i++) if((ll)(rng()%100)<p) mask[i]=1;
            for(auto &a:can) freq[solve(a,mask,flag)]++;
            for(auto &[a,b]:freq) maxi=max(maxi,b);
            if(maxi<bst) bst=maxi, bstMask=mask, bstFlag=flag;
        }
        vector<vll> temp=(bstFlag?H:V);
        for(int i=0; i<k; i++) if(bstMask[i]) temp[cand[i].first][cand[i].second]=1;
        ll res=query(temp,n); vector<bitset<MAXN>> nCan;
        for(auto &a:can) if(solve(a,bstMask,bstFlag)==res) nCan.push_back(a);
        swap(can,nCan);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...