oj.uz

Submission #43879

# Submission time Handle Problem Language Result Execution time Memory
43879 2018-03-27T01:14:20 Z ngkan146 Zagonetka (COI18_zagonetka) C++11
100 / 100
 209 ms 732 KB 
#include <bits/stdc++.h>
using namespace std;
int n, a[105];
int rev[105];
int edge[105][105];
int b[105];
// topo sort
int degin[105];
bool check(vector<int> &lst,int bound){
    for(int i=1;i<=n;i++)
        b[i] = a[i],
        degin[i] = 0;

    for(auto x: lst)
        for(auto y: lst)
            degin[y] += edge[x][y];
    queue <int> q;
    for(auto x: lst)
        if (!degin[x])  q.push(x);
    while(q.size()){
        int u = q.front();
        q.pop();
        b[u] = bound--;
        for(auto v:lst){
            if (edge[u][v]){
                degin[v] --;
                if (!degin[v])
                    q.push(v);
            }
        }
    }

    for(auto v: lst){
        if (degin[v])   return 1;
    }

    cout << "query ";   for(int i=1;i<=n;i++)   cout << b[i] << ' '; cout << endl;
    int res;
    cin >> res;
    return res;
}
bool called[105];
int CNT;
int cal(int x){
    called[x] = 1;
    while(1){
        bool ok = 0;
        for(int i=1;i<=n;i++)
            if (!called[i] && edge[x][i])
                ok = 1,
                cal(i);
        if (!ok)    break;
    }
    b[x] = ++CNT;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> a[i],
        rev[a[i]] = i;

    for(int gap=1;gap<n;gap++){
        for(int id=1;id<=n-gap;id++){
            vector <int> lst;

            for(int i=1;i<=n;i++){
                if (id <= a[i] && a[i] <= id+gap)
                    lst.push_back(i);
            }

            // condition
            edge[rev[id]][rev[id+gap]] = 1;
            edge[rev[id+gap]][rev[id]] = !check(lst, id+gap);
            edge[rev[id]][rev[id+gap]] = 0;
        }
    }
    cout << "end" << endl;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int l=1;l<=n;l++){
                    if (edge[i][j] && edge[j][l])
                        edge[i][l] = 1;
                }
    }
    for(int i=1;i<=n;i++)
        edge[0][i] = 1;
    cal(0);
    for(int i=1;i<=n;i++)   cout << b[i] << ' '; cout << endl;

    CNT = 0;
    for(int i=1;i<=n;i++)   called[i] = 0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            swap(edge[i][j], edge[j][i]);
    cal(0);
    for(int i=1;i<=n;i++)   cout << n+1-b[i] << ' '; cout << endl;
}

Compilation message

zagonetka.cpp: In function 'int cal(int)':
zagonetka.cpp:55:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n;i++)   cout << b[i] << ' '; cout << endl;
     ^~~
zagonetka.cpp:89:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i=1;i<=n;i++)   cout << b[i] << ' '; cout << endl;
                                                  ^~~~
zagonetka.cpp:97:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n;i++)   cout << n+1-b[i] << ' '; cout << endl;
     ^~~
zagonetka.cpp:97:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i=1;i<=n;i++)   cout << n+1-b[i] << ' '; cout << endl;
                                                      ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 488 KB Output is correct
7 Correct 2 ms 496 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 496 KB Output is correct
2 Correct 45 ms 496 KB Output is correct
3 Correct 58 ms 496 KB Output is correct
4 Correct 60 ms 496 KB Output is correct
5 Correct 15 ms 496 KB Output is correct
6 Correct 64 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 52 ms 512 KB Output is correct
10 Correct 22 ms 568 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 716 KB Output is correct
2 Correct 209 ms 716 KB Output is correct
3 Correct 157 ms 716 KB Output is correct
4 Correct 110 ms 716 KB Output is correct
5 Correct 156 ms 716 KB Output is correct
6 Correct 158 ms 716 KB Output is correct
7 Correct 111 ms 732 KB Output is correct
8 Correct 136 ms 732 KB Output is correct
9 Correct 135 ms 732 KB Output is correct
10 Correct 191 ms 732 KB Output is correct
11 Correct 154 ms 732 KB Output is correct
12 Correct 155 ms 732 KB Output is correct
13 Correct 185 ms 732 KB Output is correct
14 Correct 167 ms 732 KB Output is correct
15 Correct 195 ms 732 KB Output is correct
16 Correct 165 ms 732 KB Output is correct