oj.uz

Submission #640919

# Submission time Handle Problem Language Result Execution time Memory
640919 2022-09-15T14:21:58 Z hotboy2703 Zagonetka (COI18_zagonetka) C++14
78 / 100
 332 ms 464 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];
//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;
            if (new_g[i][j] == 3){

                new_g[i][j] = 2;
                new_g[j][i] = 1;
                for (int k = 1;k <= n;k ++){
                    if (new_g[i][k] == 1){
                        new_g[j][k] = 1;
                        new_g[k][j] = 2;
                    }
                }
                for (int k = 1;k <= n;k ++){
                    if (new_g[j][k] == 2){
                        new_g[i][k] = 2;
                        new_g[k][i] = 1;
                    }
                }
            }
            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;
            if (new_g[i][j] == 3){
                new_g[i][j] = 1;
                new_g[j][i] = 2;
                for (int k = 1;k <= n;k ++){
                    if (new_g[i][k] == 2){
                        new_g[j][k] = 2;
                        new_g[k][j] = 1;
                    }
                }
                for (int k = 1;k <= n;k ++){
                    if (new_g[j][k] == 1){
                        new_g[i][k] = 1;
                        new_g[k][i] = 2;
                    }
                }
            }
            ans[i] -= (new_g[i][j] == 2);
        }
        cout<<ans[i];
        if (i < n)cout<<' ';
    }
    cout<<endl;


    return 0;
}

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 320 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 336 KB Output is correct
2 Correct 60 ms 336 KB Output is correct
3 Correct 93 ms 336 KB Output is correct
4 Correct 96 ms 336 KB Output is correct
5 Correct 15 ms 328 KB Output is correct
6 Correct 96 ms 336 KB Output is correct
7 Correct 10 ms 336 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 88 ms 336 KB Output is correct
10 Correct 30 ms 336 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 348 KB Output is correct
2 Correct 332 ms 344 KB Output is correct
3 Correct 267 ms 340 KB Output is correct
4 Correct 6 ms 464 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 8 ms 368 KB Output is correct
7 Correct 61 ms 344 KB Output is correct
8 Correct 111 ms 456 KB Output is correct
9 Correct 81 ms 344 KB Output is correct
10 Correct 326 ms 340 KB Output is correct
11 Correct 258 ms 352 KB Output is correct
12 Correct 230 ms 344 KB Output is correct
13 Correct 302 ms 344 KB Output is correct
14 Correct 294 ms 344 KB Output is correct
15 Correct 317 ms 344 KB Output is correct
16 Correct 287 ms 344 KB Output is correct