oj.uz

Submission #640936

# Submission time Handle Problem Language Result Execution time Memory
640936 2022-09-15T15:05:25 Z hotboy2703 Zagonetka (COI18_zagonetka) C++17
100 / 100
 330 ms 420 KB 
#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
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 0 ms 208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Output is correct
2 Correct 66 ms 344 KB Output is correct
3 Correct 78 ms 336 KB Output is correct
4 Correct 89 ms 348 KB Output is correct
5 Correct 16 ms 340 KB Output is correct
6 Correct 96 ms 420 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 10 ms 336 KB Output is correct
9 Correct 73 ms 340 KB Output is correct
10 Correct 28 ms 336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 7 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 8 ms 332 KB Output is correct
7 Correct 5 ms 336 KB Output is correct
8 Correct 9 ms 336 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 3 ms 208 KB Output is correct
11 Correct 8 ms 332 KB Output is correct
12 Correct 9 ms 336 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 344 KB Output is correct
2 Correct 330 ms 344 KB Output is correct
3 Correct 284 ms 344 KB Output is correct
4 Correct 8 ms 360 KB Output is correct
5 Correct 10 ms 336 KB Output is correct
6 Correct 12 ms 368 KB Output is correct
7 Correct 66 ms 348 KB Output is correct
8 Correct 108 ms 352 KB Output is correct
9 Correct 86 ms 348 KB Output is correct
10 Correct 313 ms 344 KB Output is correct
11 Correct 252 ms 360 KB Output is correct
12 Correct 263 ms 348 KB Output is correct
13 Correct 318 ms 344 KB Output is correct
14 Correct 277 ms 348 KB Output is correct
15 Correct 314 ms 340 KB Output is correct
16 Correct 267 ms 336 KB Output is correct