제출 #1338917

#제출 시각아이디문제언어결과실행 시간메모리
1338917athenaLight Bulbs (EGOI24_lightbulbs)C++20
0 / 100
4094 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int n;
int query(vector<string>&out)
{
    cout<<"?"<<endl;
    for(auto ii:out)
    cout<<ii<<endl;
   // cout<<endl;
    int x;
    cin>>x;
    return x;
}
bool same(int x,int y,int i,int j)
{
  vector<string>out(n,string(n,'0'));
  out[x][y]='1';
  out[i][j]='1';
  return (query(out)%n==0);
}
vector<string> build(char type)
{
    vector<string> grid(n,string(n,type));
    grid[0][0]=type;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==0&&j==0)continue;
            if(same(0,0,i,j))
                grid[i][j]=type;
            else
            {
                if(type=='H')
                    grid[i][j]='V';
                else
                    grid[i][j]='H';
            }

        }
    }
   return grid;
}
vector<string> recons(const vector<string>&grid,vector<vector<int>>&dp) {
    vector<string>out(n,string(n,'0'));
    int i=0,j=0;
    while (i<n&&j<n) {
        bool ok=false;
        if (dp[i][j]==dp[i+1][j]+1) {
            for (int J=j;J<n;J++) {
                if (grid[i][J]=='H') {
                    out[i][J]='1';
                    i++;
                    ok=true;
                    break;
                }
            }
        }
        if (!ok&&dp[i][j]==dp[i][j+1]+1){
            for (int I=i;I<n;I++){
                if (grid[I][j]=='V') {
                    out[I][j]='1';
                    j++;
                    ok=true;
                    break;
                }
            }
        }
    }
    return out;
}
int32_t main() {
  //  int n;
    cin>>n;
    vector<vector<int>>grid(n,vector<int>(n));
    //assume 0,0 as something
    vector<char>assume={'H','V'};
    for(char t:assume)
    {
        //build a grid based on how it responds do that
        vector<string> grid=build(t);
        //build a dp to check our ans and to output positions
        vector<vector<int>>dp(n+1,vector<int>(n+1,1e18));
        for(int i=n;i>=0;i--)
        {
            for(int j=n;j>=0;j--)
            {
                if(i==n||j==n)
                {
                    dp[i][j]=0;
                    continue;
                }

                for(int J=j;J<n;J++)
                {
                  if(grid[i][J]=='H')
                  {
                     dp[i][j]=min(dp[i][j],dp[i+1][J]+1);
                  }
                }
                for(int I=i;I<n;I++)
                {
                    if(grid[I][j]=='V')
                    {
                        dp[i][j]=min(dp[i][j],dp[I][j+1]+1);
                    }
                }
            }
        }
        //rebuild
        vector<string>out=recons(grid,dp);
        //test
        if(query(out)==n*n)
        {
            cout<<"!"<<endl;
            for(auto i:out)
                cout<<i<<endl;
            cout<<endl;
            return 0;
        }
    }
    
    
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...