Submission #1364199

#TimeUsernameProblemLanguageResultExecution timeMemory
1364199avahwLight Bulbs (EGOI24_lightbulbs)C++20
0 / 100
0 ms440 KiB
#include <bits/stdc++.h>
using namespace std;

int query(int n, set<pair<int, int>>& ons){
    cout << "?\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(ons.find({i, j}) == ons.end()){
                cout << "0 ";
            }
            else cout << "1 ";
        }
        cout << "\n";
    }
    cout.flush();
    int res;
    cin >> res;
    return res;
}

void ans(int n, set<pair<int, int>>& ons){
    cout << "!\n";
    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(ons.find({i, j}) == ons.end()){
            cout << "0 ";
        }
        else cout << "1 ";
    }
    cout << "\n";
    }
    cout.flush();
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<vector<int>> dir(n, vector<int>(n, -1));
    // 0 = horizontal, 1 = vertical, -1 = unknown
    // if any return n, they are both horizontal. all bulbs that return 2n - 1 are vertical
    // if any return 2n, both are vertical any that return 2n - 1 are horizontal
    // if they all return 2n -1, try every bulb in row except first. 
    // if n lit, row is horizontal and first is vertical
    // if n(n -1) lit, row is vertical and first is horizontal
    for(int i = 0; i < n; i++){
        vector<int> results(n);
        for(int j = 1; j < n; j++){
            set<pair<int, int>> ons;
            ons.insert({i, 0});
            ons.insert({i, j});
            results[j] = query(n, ons);
            if(results[i] == n){
                dir[i][0] = 0;
                dir[i][j] = 0;
            }
            else if(results[j] == 2*n){
                dir[i][0] = 1;
                dir[i][j] = 1;
            }
        }
        // if first is horizontal
        if(dir[i][0] == 0){
            for(int j = 1; j < n; j++){
                if(results[j] == n) dir[i][j] = 0;
                else dir[i][j] = 1;
            }
        }
        // if first is vertical
        if(dir[i][0] == 1){
            for(int j = 1; j < n; j++){
                if(results[j] == 2*n){
                    dir[i][j] = 1;
                }
                else dir[i][j] = 0;
            }
        }
        // if first is undetermined
        if(dir[i][0] == -1){
            set<pair<int, int>> e;
            for(int j = 1; j < n; j++) e.insert({i, j});
            int res = query(n, e);
            if(res == n){
                for(int j = 1; j < n; j++) dir[i][j] = 0;
                dir[i][0] = 1;
            }
            else{
                for(int j = 1; j < n; j++) dir[i][j] = 1;
                dir[i][0] = 0;
            }
        }
    }
    // for(auto item : dir){
    //     for(auto a : item){
    //         cout << a << " ";
    //     }
    //     cout << "\n";
    // }
    
    set<pair<int, int>> h_found;
    for(int i = 0; i < n; i++){
        bool found = false;
        // find the horizontal in that row
        // if there's no horizontal, light up that whole row
        for(int j = 0; j < n; j++){
            if(dir[i][j] == 0) {
                h_found.insert({i, j});
                found = true;
                break;
            }
        }
        if(!found){
                set<pair<int, int>> stuff;
                for(int j = 0; j < n; j++){
                    stuff.insert({i, j});
                }
                ans(n, stuff);
                return 0;
            }
    }
    ans(n, h_found);
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...