oj.uz

Submission #640763

# Submission time Handle Problem Language Result Execution time Memory
640763 2022-09-15T07:52:34 Z uylulu Zagonetka (COI18_zagonetka) C++14
18 / 100
 116 ms 320 KB 
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 100;

bool check = false,adj[N + 1][N + 1],temp[N + 1][N + 1],vis[N + 1];
int deg[N + 1],num[N + 1],pos[N + 1],n;
vector<int> topo;

void init(int l,int r) {
    for(int i = 1;i <= n;i++) {
        deg[i] = 0;
        vis[i] = false;
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) temp[i][j] = false;
    }

    for(int i = l;i <= r;i++) {
        for(int j = l;j <= r;j++) {
            temp[pos[i]][pos[j]] = adj[pos[i]][pos[j]];
            if(adj[pos[i]][pos[j]]) {
                deg[pos[j]]++;
            }
        }
    }
    check = true;
}

void dfs(int s) {
    if(vis[s]) {
        check = false;
        return;
    }
    topo.push_back(s);
    vis[s] = true;
    for(int i = 1;i <= n;i++) {
        if(temp[s][i]) {
            dfs(i);
        }
    }
}

int res[N + 1];

int query() {
    for(int i = 0;i < topo.size();i++) {
        res[topo[i]] = i + 1;
    }
    cout<<"query ";
    for(int i = 1;i <= n;i++) cout<<res[i]<<" ";
    cout<<endl;
    int x;
    cin>>x;
    return x;
}

void small() {
    priority_queue<int> q;
    vector<int> kq;
    for(int i = 1;i <= n;i++) {
        if(deg[i] == 0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int s = q.top();
        vis[s] = true;
        q.pop();
        kq.push_back(s);
        for(int i = 1;i <= n;i++) {
            if(vis[i]) continue;
            if(adj[s][i]) {
                vis[i] = true;
                q.push(i);
            }
        }
    }
    reverse(kq.begin(),kq.end());
    for(int i = 0;i < kq.size();i++) {
        res[kq[i]] = i + 1;
    }
    for(int i = 1;i <= n;i++) cout<<res[i]<<" ";
    cout<<endl;
}

void big() {
    priority_queue<int> q;
    for(int i = 1;i <= n;i++) {
        if(deg[i] == 0) {
            q.push(i);
        }
    }
    vector<int> kq;
    while(!q.empty()) {
        int s = q.top();
        kq.push_back(s);
        q.pop();
        vis[s] = true;
        for(int i = 1;i <= n;i++) {
            if(vis[i]) continue;
            if(adj[s][i]) {
                q.push(i);
            }
        }
    }
    for(int i = 0;i < kq.size();i++) {
        res[kq[i]] = i + 1;
    }
    for(int i = 1;i <= n;i++) cout<<res[i]<<" ";
    cout<<endl;
}

int main() {
    cin>>n;
    for(int i = 1;i <= n;i++) {
        cin>>num[i];
        pos[num[i]] = i;
    }
    for(int len = 1;len <= n - 1;len++) {
        for(int p = 1;p + len <= n;p++) {
            adj[pos[p + len]][pos[p]] = true;
            init(p,p + len);
            topo.clear();
            for(int i = 1;i < p;i++) {
                topo.push_back(pos[i]);
            }
            int cnt = 0;
            for(int i = p;i <= p + len;i++) {
                if(deg[pos[i]] == 0) {
                    cnt++;
                    dfs(pos[i]);
                }
            }
            for(int i = p + len + 1;i <= n;i++) {
                topo.push_back(pos[i]);
            }
            adj[pos[p + len]][pos[p]] = false;
            if(cnt == 0 || !check || !query()) {
                adj[pos[p]][pos[p + len]] = true;
            }
        }
    }
    
    for(int i = 1;i <= n;i++) {
        for(int j = i + 1;j <= n;j++) {
            if(adj[i][j]) {
                adj[j][i] = true;
                adj[i][j] = false;
            } else if(adj[j][i]) {
                adj[i][j] = true;
                adj[j][i] = false;
            }
        }
    }
    init(1,n);
    cout<<"end"<<endl;
    small();
    for(int i = 1;i <= n;i++) {
        for(int j = i + 1;j <= n;j++) {
            if(adj[i][j]) {
                adj[j][i] = true;
                adj[i][j] = false;
            } else if(adj[j][i]) {
                adj[i][j] = true;
                adj[j][i] = false;
            }
        }
    }
    init(1,n);
    big();
    exit(0);

    return 0;
}

Compilation message

zagonetka.cpp: In function 'int query()':
zagonetka.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0;i < topo.size();i++) {
      |                   ~~^~~~~~~~~~~~~
zagonetka.cpp: In function 'void small()':
zagonetka.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0;i < kq.size();i++) {
      |                   ~~^~~~~~~~~~~
zagonetka.cpp: In function 'void big()':
zagonetka.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0;i < kq.size();i++) {
      |                   ~~^~~~~~~~~~~

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 Integer 6 violates the range [1, 4]
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 34 ms 208 KB Output is correct
3 Correct 28 ms 316 KB Output is correct
4 Correct 46 ms 208 KB Output is correct
5 Correct 11 ms 208 KB Output is correct
6 Correct 32 ms 320 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 8 ms 208 KB Output is correct
9 Correct 37 ms 208 KB Output is correct
10 Correct 16 ms 208 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 1 ms 208 KB Integer 117 violates the range [1, 20]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 300 KB Integer 102 violates the range [1, 93]
2 Halted 0 ms 0 KB -