Submission #1361399

#TimeUsernameProblemLanguageResultExecution timeMemory
1361399talyLight Bulbs (EGOI24_lightbulbs)C++20
83.65 / 100
40 ms540 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define tii tuple<int, int, int>
using namespace std;
#define rsz resize
#define sz size
#define ass assign
#define all(x) (x).begin(),(x).end()
int n;
vector<vector<int>> mat;
vector<int> lig_lin, lig_col;
vector<pii> lin, col;
set<int> lin_liv, col_liv;
// map<pair<pii, pii>, int> mp;
int ln, cl;
pii c={-1, -1};
int d=0;

int ask(){
    // pii a, b;
    // for(int i=0; i<n; i++){
    //     for(int j=0; j<n; j++){
    //         if(mat[i][j]){
    //             b=a;
    //             a={i, j};
    //         }
    //     }
    // }
    // if(mp[{a, b}])return mp[{a, b}];
    cout << "?"<<endl;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << mat[i][j];
        }
        cout << endl;
    }
    int r; cin >> r;
    // mp[{a, b}]=r;
    // mp[{b, a}]=r;
    return r;
}

void add(int x, int y, int dir){
    if(dir==1){
        if(!lig_col[y]){
            lig_col[y]=1;
            cl--;
            col.pb({x, y});
            if(c.ff==-1){
                c={x, y};
                d=dir;
            }
            col_liv.erase(y);
        }
    }else{
        if(!lig_lin[x]){
            lig_lin[x]=1;
            ln--;
            lin.pb({x, y});
            if(c.ff==-1){
                c={x, y};
                d=dir;
            }
            lin_liv.erase(x);
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    mat.rsz(n, vector<int>(n));
    lig_lin.rsz(n);
    lig_col.rsz(n);
    ln=n, cl=n;
    vector<pair<pii, pii>> sem_resp;
    for(int i=0; i<n; i++){
        lin_liv.insert(i);
        col_liv.insert(i);
    }
    srand(time(0));
    while(ln>0&&cl>1){
        int k1=rand()%ln;
        int k2=rand()%cl;
        int k3=rand()%cl;
        while(k3==k2){
            k3=rand()%cl;
        }

        int x, y, z;

        auto it1=lin_liv.begin();
        while(k1--){
            it1++;
        }
        x=*(it1);

        auto it2=col_liv.begin();
        while(k2--){
            it2++;
        }
        y=*(it2);

        auto it3=col_liv.begin();
        while(k3--){
            it3++;
        }
        z=*(it3);

        mat[x][y]=1;
        mat[x][z]=1;
        int r=ask();
        mat[x][y]=0;
        mat[x][z]=0;
        if(r==2*n){
            add(x, y, 1);
            add(x, z, 1);
            if(!sem_resp.empty()){
                // sem_resp.pb({{x, y}, {x, z}});
                for(auto [p1, p2]:sem_resp){
                    mat[p1.ff][p1.ss]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[p1.ff][p1.ss]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(p1.ff, p1.ss, d*(-1));
                        add(p2.ff, p2.ss, d);
                    }else{
                        add(p1.ff, p1.ss, d);
                        add(p2.ff, p2.ss, d*(-1));
                    }
                }
                sem_resp={};
            }
        }else if(r==n){
            add(x, y, -1);
            if(!sem_resp.empty()){
                // sem_resp.pb({{x, y}, {x, z}});
                for(auto [p1, p2]:sem_resp){
                    mat[p1.ff][p1.ss]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[p1.ff][p1.ss]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(p1.ff, p1.ss, d*(-1));
                        add(p2.ff, p2.ss, d);
                    }else{
                        add(p1.ff, p1.ss, d);
                        add(p2.ff, p2.ss, d*(-1));
                    }
                }
                sem_resp={};
            }
        }else{
            if(c.ff==-1){
                sem_resp.pb({{x, y}, {x, z}});
            }else{
                if(sem_resp.empty()){
                    mat[x][y]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[x][y]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(x, y, d*(-1));
                        add(x, z, d);
                    }else{
                        add(x, y, d);
                        add(x, z, d*(-1));
                    }
                }else{
                    sem_resp.pb({{x, y}, {x, z}});
                    for(auto [p1, p2]:sem_resp){
                        mat[p1.ff][p1.ss]=1;
                        mat[c.ff][c.ss]=1;
                        int r2=ask();
                        mat[p1.ff][p1.ss]=0;
                        mat[c.ff][c.ss]=0;
                        if(r2==2*n-1){
                            add(p1.ff, p1.ss, d*(-1));
                            add(p2.ff, p2.ss, d);
                        }else{
                            add(p1.ff, p1.ss, d);
                            add(p2.ff, p2.ss, d*(-1));
                        }
                    }
                    sem_resp={};
                }
            }
        }
    }
    while(ln>1&&cl>0){
        int k1=rand()%cl;
        int k2=rand()%ln;
        int k3=rand()%ln;
        while(k3==k2){
            k3=rand()%ln;
        }

        int x, y, z;

        auto it1=col_liv.begin();
        while(k1--){
            it1++;
        }
        x=*(it1);

        auto it2=lin_liv.begin();
        while(k2--){
            it2++;
        }
        y=*(it2);

        auto it3=lin_liv.begin();
        while(k3--){
            it3++;
        }
        z=*(it3);

        mat[y][x]=1;
        mat[z][x]=1;
        int r=ask();
        mat[y][x]=0;
        mat[z][x]=0;
        if(r==2*n){
            add(y, x, -1);
            add(z, x, -1);
            if(!sem_resp.empty()){
                // sem_resp.pb({{y, x}, {z, x}});
                for(auto [p1, p2]:sem_resp){
                    mat[p1.ff][p1.ss]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[p1.ff][p1.ss]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(p1.ff, p1.ss, d*(-1));
                        add(p2.ff, p2.ss, d);
                    }else{
                        add(p1.ff, p1.ss, d);
                        add(p2.ff, p2.ss, d*(-1));
                    }
                }
                sem_resp={};
            }
        }else if(r==n){
            add(y, x, 1);
            if(!sem_resp.empty()){
                // sem_resp.pb({{y, x}, {z, x}});
                for(auto [p1, p2]:sem_resp){
                    mat[p1.ff][p1.ss]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[p1.ff][p1.ss]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(p1.ff, p1.ss, d*(-1));
                        add(p2.ff, p2.ss, d);
                    }else{
                        add(p1.ff, p1.ss, d);
                        add(p2.ff, p2.ss, d*(-1));
                    }
                }
                sem_resp={};
            }
        }else{
            if(c.ff==-1){
                sem_resp.pb({{y, x}, {z, x}});
            }else{
                if(sem_resp.empty()){
                    mat[y][x]=1;
                    mat[c.ff][c.ss]=1;
                    int r2=ask();
                    mat[y][x]=0;
                    mat[c.ff][c.ss]=0;
                    if(r2==2*n-1){
                        add(y, x, d*(-1));
                        add(z, x, d);
                    }else{
                        add(y, x, d);
                        add(z, x, d*(-1));
                    }
                }else{
                    sem_resp.pb({{y, x}, {z, x}});
                    for(auto [p1, p2]:sem_resp){
                        mat[p1.ff][p1.ss]=1;
                        mat[c.ff][c.ss]=1;
                        int r2=ask();
                        mat[p1.ff][p1.ss]=0;
                        mat[c.ff][c.ss]=0;
                        if(r2==2*n-1){
                            add(p1.ff, p1.ss, d*(-1));
                            add(p2.ff, p2.ss, d);
                        }else{
                            add(p1.ff, p1.ss, d);
                            add(p2.ff, p2.ss, d*(-1));
                        }
                    }
                    sem_resp={};
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(!lig_lin[i]&&!lig_col[j]){
                mat[c.ff][c.ss]=1;
                mat[i][j]=1;
                int r=ask();
                mat[c.ff][c.ss]=0;
                mat[i][j]=0;
                if(r==2*n-1){
                    add(i, j, d*(-1));
                }else{
                    add(i, j, d);
                }
            }
        }
    }
    cout << "!"<<endl;
    if(lin.sz()==n){
        for(auto [a, b]:lin){
            mat[a][b]=1;
        }
    }else{
        for(auto [a, b]:col){
            mat[a][b]=1;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << mat[i][j];
        }
        cout << endl;
    }
    // cout << " "<<lin.sz()<<" "<<col.sz()<<" ";
    // cout << ln << " "<<cl<<endl;
}
// 00000
// 01000
// 10100
// 00000
// 00011
// 4 5 1 0
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...