oj.uz

Submission #640914

# Submission time Handle Problem Language Result Execution time Memory
640914 2022-09-15T14:11:40 Z hotboy2703 Zagonetka (COI18_zagonetka) C++17
18 / 100
 390 ms 368 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;
                    }
                }
                for (int k = 1;k <= n;k ++){
                    if (new_g[j][k] == 2){
                        new_g[i][k] = 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;
            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;
                    }
                }
                for (int k = 1;k <= n;k ++){
                    if (new_g[j][k] == 1){
                        new_g[i][k] = 1;
                    }
                }
            }
            ans[i] -= (new_g[i][j] == 2);
        }
        cout<<ans[i];
        if (i < n)cout<<' ';
    }
    cout<<endl;


    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 336 KB Output is correct
2 Correct 68 ms 336 KB Output is correct
3 Correct 90 ms 332 KB Output is correct
4 Correct 97 ms 336 KB Output is correct
5 Correct 17 ms 336 KB Output is correct
6 Correct 92 ms 340 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 77 ms 344 KB Output is correct
10 Correct 32 ms 336 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 348 KB Output is correct
2 Correct 366 ms 344 KB Output is correct
3 Correct 279 ms 344 KB Output is correct
4 Correct 7 ms 356 KB Output is correct
5 Correct 10 ms 368 KB Output is correct
6 Correct 10 ms 348 KB Output is correct
7 Correct 72 ms 356 KB Output is correct
8 Correct 119 ms 348 KB Output is correct
9 Correct 85 ms 344 KB Output is correct
10 Incorrect 390 ms 356 KB Output isn't correct
11 Halted 0 ms 0 KB -