Submission #640749

#	Time	Username	Problem	Language	Result	Execution time	Memory
640749		hotboy2703	Zagonetka (COI18_zagonetka)	C++17	0 / 100	286 ms	336 KiB

zagonetka

#include<bits/stdc++.h>
using namespace std;
int n;
int p[110];
int id[110];
int g[110][110];
int ans[110];
int cnt[110];
//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;
    memset(ans,0,sizeof ans);
    for (int i = 1;i <= n;i ++){
        for (int j = 1;j <= n;j ++){
            if (i != j){
                if (g[i][j] == 1){ans[i]++;}
                if (g[i][j] == 3){
                    if (i > j)ans[i]++;
                }
            }
        }
        ans[i]++;
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    memset(ans,0,sizeof ans);
    for (int i = 1;i <= n;i ++){
        for (int j = 1;j <= n;j ++){
            if (i != j){
                if (g[i][j] == 1){ans[i]++;}
                if (g[i][j] == 3){
                    if (i < j)ans[i]++;
                }
            }
        }
        ans[i]++;
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}

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