Submission #640936

#TimeUsernameProblemLanguageResultExecution timeMemory
640936hotboy2703Zagonetka (COI18_zagonetka)C++17
100 / 100
330 ms420 KiB
#include<bits/stdc++.h>
using namespace std;
int n;
int p[110];
int id[110];
int g[110][110];
int new_g[110][110];
int ans[110];
int cnt[110];
bool shit[110];
void update(int i,int j,int x){
    if (new_g[i][j] == 3){
        new_g[i][j] = x;
        new_g[j][i] = 3 - x;
        for (int k = 1;k <= n;k ++){
                    if (new_g[i][k] == 3-x){
                        update(j,k,3-x);
                    }
                }
                for (int k = 1;k <= n;k ++){
                    if (new_g[j][k] == x){
                        update(i,k,x);
                    }
                }
    }
}
//1 - big, 2 - small,3 - neutral
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for (int i = 1;i <= n;i ++){
        cin>>p[i];
        id[p[i]] = i;
    }
    for (int i = 1;i <= n;i ++){
        for (int j = 1;j <= n;j ++){
            if (i == j)continue;
            g[i][j] = (p[i] > p[j]) ? (1) : (2);
        }
    }
    for (int k = 1;k <= n - 1;k ++){
        for (int i = 1;i + k <= n;i ++){
            int j = i + k;
            bool ok = 0;
            for (int x = i+1;x < j; x++){
                if (g[id[i]][id[x]] == g[id[x]][id[j]] && g[id[i]][id[x]] != 3){
                    ok = 1;
                    break;
                }
            }
            if (!ok){
                g[id[i]][id[j]] = 3 - g[id[i]][id[j]];
                g[id[j]][id[i]] = 3 - g[id[j]][id[i]];
                //cout<<"MOMJOKE"<<' '<<id[i]<<' '<<id[j]<<' '<<i<<' '<<j<<'\n';
                memset(ans,0,sizeof ans);
                memset(cnt,0,sizeof cnt);
                for (int x = 1; x <= n;x ++)for (int y = 1;y <= n;y ++)if (x != y)cnt[x] += (g[x][y] == 1);
                //for (int x = 1; x <= n;x ++){for (int y = 1;y <= n;y ++)cout<<g[x][y]<<' ';cout<<endl;}
                queue <int> q;
                for (int x = 1;x <= n;x ++){
                    if (cnt[x] == 0){
                        q.push(x);
                    }
                }
                int cur = 1;
                while (!q.empty()){
                    int u = q.front();
                    q.pop();
                    ans[u] = cur;
                    cur++;
                    for (int v = 1;v <= n; v ++){
                        if (v == u)continue;
                        cnt[v] -= (g[v][u] == 1);
                        if (cnt[v] == 0 && (g[v][u] == 1))q.push(v);
                    }
                }
                cout<<"query";
                for (int x = 1;x <= n;x ++)cout<<' '<<ans[x];
                cout<<endl;
                g[id[i]][id[j]] = 3 - g[id[i]][id[j]];
                g[id[j]][id[i]] = 3 - g[id[j]][id[i]];
                int res;
                cin>>res;
                if (res == 1){
                    g[id[i]][id[j]] = 3;
                    g[id[j]][id[i]] = 3;
                }
            }
        }
    }
    cout<<"end"<<endl;
    for (int i = 1;i <= n;i ++){
        for (int j = 1;j <= n;j ++){
            new_g[i][j] = g[i][j];
        }
    }
    for (int i = 1;i <= n;i ++){
        ans[i] = 1;
        for (int j = 1;j <= n;j ++){
            if (i == j)continue;
            update(i,j,2);
            ans[i] += (new_g[i][j] == 1);
        }

        cout<<ans[i];
        if (i < n)cout<<' ';
    }
    cout<<endl;
    for (int i = 1;i <= n;i ++){
        for (int j = 1;j <= n;j ++){
            new_g[i][j] = g[i][j];
        }
    }
    for (int i = 1;i <= n;i ++){
        ans[i] = n;
        for (int j = 1;j <= n;j ++){
            if (i == j)continue;
            update(i,j,1);
            ans[i] -= (new_g[i][j] == 2);
        }
        cout<<ans[i];
        if (i < n)cout<<' ';
    }
    cout<<endl;


    return 0;
}
/*
5
3 4 2 5 1
5 2
5 1
3 4
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...