Submission #1158987

#TimeUsernameProblemLanguageResultExecution timeMemory
1158987Tyx2019Light Bulbs (EGOI24_lightbulbs)C++20
80 / 100
75 ms604 KiB
#include <bits/stdc++.h>
#define int long long
#define debug(x) if(0) cerr << #x << " = " << x << endl;
using namespace std;
const int maxN = 105;
int N;
int qrything[maxN][maxN];
int weirdX[maxN], weirdY[maxN];
void add(int i, int j){
    qrything[i][j] = 1;
}
int ask(){
    cout << "?\n";
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++) cout << qrything[weirdX[i]][weirdY[j]];
        cout << endl;
    }
    memset(qrything, 0, sizeof(qrything));
    int k;
    cin >> k;
    return k;
}
vector<int> unfoundrow, unfoundcol;
vector<int> foundrow, foundcol;
int rowguy[maxN];
int colguy[maxN];
void rowfound(int row, int col){
    rowguy[row] = col;
    auto it = find(unfoundrow.begin(), unfoundrow.end(), row);
    unfoundrow.erase(it);
    foundrow.push_back(row);
}
void colfound(int col, int row){
    colguy[col] = row;
    auto it = find(unfoundcol.begin(), unfoundcol.end(), col);
    unfoundcol.erase(it);
    foundcol.push_back(col);
}
bool get(int a, int b){
    add(1, a);
    add(1, b);
    int res = ask();
    if(res == N){
        rowfound(1, a);
        return 1;
    }
    else if(res == 2 * N){
        colfound(a, 1);
        colfound(b, 1);
        return 1;
    }
    return 0;
}
mt19937 rng(23);
signed main(){
    cin >> N;
  for(int i=1;i<=N;i++) weirdX[i] = i;
  for(int i=1;i<=N;i++) weirdY[i] = i;
  shuffle(weirdX+1, weirdX + N+1, rng);
  shuffle(weirdY+1, weirdY + N+1, rng);
    unfoundrow.clear();
    unfoundcol.clear();
    foundrow.clear();
    foundcol.clear();
    memset(rowguy, -1, sizeof(rowguy));
    memset(colguy, -1, sizeof(colguy));
    for(int i=1;i<=N;i++){
        unfoundrow.push_back(i);
        unfoundcol.push_back(i);
    }
    if(!get(1, 2)){
        if(!get(2, 3)){
            if(!get(1, 3)) cout << "Dieded\n";
        }
    }
    debug("HI")
    while(!unfoundcol.empty() && !unfoundrow.empty()){
        debug("hi")
        int c = unfoundcol[0];
        int r = unfoundrow[0];
        if(!foundcol.empty()){
          debug(foundcol.size())
            add(r, c);
            debug(colguy[foundcol[0]])
            debug(foundcol[0]);
            add(colguy[foundcol[0]], foundcol[0]);
            int res = ask();
            if(res == 2*N){
                colfound(c, r);
            }
            else{
                rowfound(r, c);
            }
        }
        else{
          debug(foundrow.size())
            add(r, c);
            add(foundrow[0], rowguy[foundrow[0]]);
            int res = ask();
            if(res == 2*N-1){
                colfound(c, r);
            }
            else{
                rowfound(r, c);
            }
        }
    }
    cout << "!\n";
    int res[maxN][maxN];
    memset(res, 0, sizeof(res));
    if(unfoundcol.empty()){
        for(int i=1;i<=N;i++) res[colguy[i]][i] = 1;
    }
    else{
        for(int i=1;i<=N;i++) res[i][rowguy[i]] = 1;
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++) cout << res[weirdX[i]][weirdY[j]];
        cout << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...