oj.uz

Submission #587022

# Submission time Handle Problem Language Result Execution time Memory
587022 2022-07-01T08:14:18 Z MilosMilutinovic Zagonetka (COI18_zagonetka) C++14
100 / 100
 777 ms 520 KB 
/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 07:54:35
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  auto Ask = [&](vector<int> q) {
    cout << "query ";
    for (int i = 0; i < n; i++) {
      cout << q[i] << " ";
    }
    cout << endl;
    int x;
    cin >> x;
    return x;
  };
  vector<vector<bool>> f(n, vector<bool>(n, true));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j && p[i] < p[j]) {
        f[i][j] = false;
      }
    }
  }
  auto Valid = [&]() {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j && f[i][j]) {
          g[i].push_back(j);  
        }
      }
    }
    vector<int> in(n);
    for (int i = 0; i < n; i++) {
      for (int j : g[i]) {
        in[j] += 1;
      }
    }
    vector<int> que;
    for (int i = 0; i < n; i++) {
      if (in[i] == 0) {
        que.push_back(i);
      }
    }
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        in[j] -= 1;
        if (in[j] == 0) {
          que.push_back(j);
        }
      }
    }
    reverse(que.begin(), que.end());
    vector<int> q(n);
    for (int i = 0; i < n; i++) {
      q[que[i]] = i + 1;
    }
    return Ask(q);
  };
  vector<vector<bool>> save(n, vector<bool>(n));               
  for (int it = 0; it < n * (n - 1) / 2; it++) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i != j && f[i][j]) {
          g[i].push_back(j);
        }
      }
    }
    pair<int, int> p = {-1, -1};
    for (int i = 0; i < n; i++) {
      vector<int> que(1, i);
      vector<bool> was(n);
      vector<bool> ok(n, true);
      was[i] = true;
      for (int b = 0; b < (int) que.size(); b++) {
        int x = que[b];
        for (int j : g[x]) {
          if (!was[j]) {
            was[j] = true;
            que.push_back(j);
          }
          if (x != i) {
            ok[j] = false;
          }
        }
      }
      bool found = false;
      for (int j = 0; j < n; j++) {
        if (i != j && ok[j] && f[i][j]) {
          if (!save[i][j]) {
            p = make_pair(i, j);
            save[i][j] = true;
            found = true;
            break;
          }
        }
      }
      if (found) {
        break;
      }
    }  
    if (p.first == -1) {
      break;
    }                   
    swap(f[p.first][p.second], f[p.second][p.first]);
    if (Valid()) {
      f[p.first][p.second] = f[p.second][p.first] = false;   
    } else {
      swap(f[p.first][p.second], f[p.second][p.first]);
    }
  }
  vector<pair<int, int>> c;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j && f[i][j]) {
        c.emplace_back(i, j);
      }
    }
  }
  cout << "end" << endl;
  vector<vector<int>> g(n);
  for (int i = 0; i < (int) c.size(); i++) {
    g[c[i].first].push_back(c[i].second);
  }
  vector<vector<int>> path(n);
  vector<vector<int>> par(n);
  for (int i = 0; i < n; i++) {               
    vector<bool> was(n);
    function<void(int)> Dfs = [&](int v) {
      was[v] = true;
      path[i].push_back(v);
      par[v].push_back(i);
      for (int u : g[v]) {
        if (!was[u]) {
          Dfs(u);
        }
      }
    };
    Dfs(i);
  }
  {             
    vector<int> ans(n, -1);
    function<void(vector<int>, int, int)> Dfs = [&](vector<int> v, int L, int R) {
      if (v.empty()) {
        return;
      }
      set<int> alive;
      for (int j : v) {
        alive.insert(j);
      }
      int i = *min_element(v.begin(), v.end());
      set<int> ch;
      for (int j : path[i]) {
        if (alive.find(j) != alive.end()) {
          ch.insert(j);
        }
      }
      ans[i] = L + (int) ch.size() - 1;
      vector<int> vl;
      for (int j = 0; j < (int) path[i].size(); j++) {
        if (path[i][j] != i && alive.find(path[i][j]) != alive.end()) {
          vl.push_back(path[i][j]);
        }
      }        
      vector<int> vr;
      for (int j = 0; j < (int) v.size(); j++) {
        if (ch.find(v[j]) == ch.end()) {
          vr.push_back(v[j]);
        }
      }
      Dfs(vl, L, ans[i] - 1);
      Dfs(vr, ans[i] + 1, R);
    };
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    Dfs(v, 1, n); 
    for (int i = 0; i < n; i++) {
      cout << ans[i] << " ";
    }
    cout << endl;
  }
  {             
    vector<int> ans(n, -1);
    function<void(vector<int>, int, int)> Dfs = [&](vector<int> v, int L, int R) {
      if (v.empty()) {
        return;
      }
      set<int> alive;
      for (int j : v) {
        alive.insert(j);
      }
      int i = *min_element(v.begin(), v.end());
      set<int> pr;
      for (int j : par[i]) {
        if (alive.find(j) != alive.end()) {
          pr.insert(j);
        }
      }
      ans[i] = R - (int) pr.size() + 1;
      vector<int> vl;
      for (int j = 0; j < (int) par[i].size(); j++) {
        if (par[i][j] != i && alive.find(par[i][j]) != alive.end()) {
          vl.push_back(par[i][j]);
        }
      }        
      vector<int> vr;
      for (int j = 0; j < (int) v.size(); j++) {
        if (pr.find(v[j]) == pr.end()) {
          vr.push_back(v[j]);
        }
      }
      Dfs(vl, ans[i] + 1, R);
      Dfs(vr, L, ans[i] - 1);
    };
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    Dfs(v, 1, n);
    for (int i = 0; i < n; i++) {
      cout << ans[i] << " ";
    }
    cout << endl;
  }
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 336 KB Output is correct
2 Correct 127 ms 336 KB Output is correct
3 Correct 155 ms 336 KB Output is correct
4 Correct 161 ms 464 KB Output is correct
5 Correct 26 ms 316 KB Output is correct
6 Correct 177 ms 472 KB Output is correct
7 Correct 13 ms 328 KB Output is correct
8 Correct 20 ms 320 KB Output is correct
9 Correct 156 ms 336 KB Output is correct
10 Correct 51 ms 336 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 10 ms 324 KB Output is correct
4 Correct 17 ms 308 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 12 ms 316 KB Output is correct
7 Correct 7 ms 336 KB Output is correct
8 Correct 14 ms 304 KB Output is correct
9 Correct 11 ms 328 KB Output is correct
10 Correct 4 ms 208 KB Output is correct
11 Correct 9 ms 336 KB Output is correct
12 Correct 10 ms 336 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 508 KB Output is correct
2 Correct 689 ms 520 KB Output is correct
3 Correct 594 ms 500 KB Output is correct
4 Correct 56 ms 388 KB Output is correct
5 Correct 74 ms 392 KB Output is correct
6 Correct 75 ms 400 KB Output is correct
7 Correct 401 ms 376 KB Output is correct
8 Correct 677 ms 388 KB Output is correct
9 Correct 568 ms 396 KB Output is correct
10 Correct 719 ms 516 KB Output is correct
11 Correct 673 ms 504 KB Output is correct
12 Correct 500 ms 508 KB Output is correct
13 Correct 771 ms 508 KB Output is correct
14 Correct 583 ms 508 KB Output is correct
15 Correct 749 ms 508 KB Output is correct
16 Correct 777 ms 516 KB Output is correct