Submission #1177622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177622		ZeroCool	Zagonetka (COI18_zagonetka)	C++20	100 / 100	28 ms	456 KiB

zagonetka

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define ar array
#define all(v) v.begin(), v.end()

using namespace std;





const int N = 2e2 + 20;
const int LOG = 20;
const int INF = 1e12;
const int MOD = 1e9 + 7;

void chmin(int &x,int y){x = min(x, y);};
void chmax(int &x,int y){x = max(x, y);};
void mm(int &x){x = (x % MOD + MOD) % MOD;};

int n;

bool g[N][N];
int ans[N];
int T = 1;
bool vis[N];
void dfs1(int x){
    if(vis[x])return;
    vis[x] = 1;
    for(int i = 0;i < n;i++){
        if(g[x][i])dfs1(i);
    }
    ans[x] = T++;
}

void dfs2(int x){
    if(vis[x])return;
    vis[x] = 1;
    for(int i = 0;i < n;i++){
        if(g[i][x])dfs2(i);
    }
    ans[x] = T--;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    int A[n];
    for(int i = 0;i < n;i++)cin>>A[i];
    int pos[n + 1];
    for(int i = 0;i < n;i++)pos[A[i]] = i;
    for(int i = 1;i <= n;i++){
        vector<int> X, Y{pos[i]};
        for(int j = i + 1;j <= n;j++){
            int Q[n];
            for(int x = 0;x < n;x++)Q[x] = A[x];
            int c = i;
            for(auto u: X)Q[u] = c++;
            Q[pos[j]] = c++;
            for(auto u: Y)Q[u] = c++;
            cout<<"query ";
            for(int x = 0;x < n;x++)cout<<Q[x]<<" ";
            cout<<endl;
            int k;
            cin>>k;
            g[pos[j]][pos[i]] = !k;
            if(k)X.push_back(pos[j]);
            else Y.push_back(pos[j]);
        }
    }
    cout<<"end"<<endl;
    memset(vis, 0, sizeof vis);
    T = 1;
    for(int i = 0;i < n;i++)dfs1(i);
    for(int i = 0;i < n;i++)cout<<ans[i]<<" ";
    cout<<endl;
    memset(vis, 0, sizeof vis);
    T = n;
    for(int i = 0;i < n;i++)dfs2(i);
    for(int i = 0;i < n;i++)cout<<ans[i]<<" ";
    cout<<endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51