oj.uz

Submission #44565

# Submission time Handle Problem Language Result Execution time Memory
44565 2018-04-03T09:50:46 Z ssnsarang2023 Zagonetka (COI18_zagonetka) C++17
18 / 100
 245 ms 716 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);
            }
        }
    }
 
    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;
  fflush(stdout);
  return 0;
}

Compilation message

zagonetka.cpp: In function 'int cal(int)':
zagonetka.cpp:51:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=1;i<=n;i++)   cout << b[i] << ' '; cout << endl;
     ^~~
zagonetka.cpp:85: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:93: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:93: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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 288 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Incorrect 2 ms 464 KB not a permutation
6 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 464 KB Output is correct
2 Correct 53 ms 492 KB Output is correct
3 Correct 58 ms 512 KB Output is correct
4 Correct 71 ms 520 KB Output is correct
5 Correct 18 ms 520 KB Output is correct
6 Correct 64 ms 572 KB Output is correct
7 Correct 9 ms 572 KB Output is correct
8 Correct 10 ms 572 KB Output is correct
9 Correct 46 ms 572 KB Output is correct
10 Correct 22 ms 572 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 572 KB Output is correct
2 Incorrect 2 ms 572 KB not a permutation
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 576 KB Output is correct
2 Correct 194 ms 576 KB Output is correct
3 Correct 169 ms 576 KB Output is correct
4 Correct 176 ms 620 KB Output is correct
5 Correct 235 ms 716 KB Output is correct
6 Correct 245 ms 716 KB Output is correct
7 Incorrect 106 ms 716 KB not a permutation
8 Halted 0 ms 0 KB -