oj.uz

Submission #218088

# Submission time Handle Problem Language Result Execution time Memory
218088 2020-04-01T07:32:00 Z extraterrestrial Library (JOI18_library) C++14
100 / 100
 247 ms 508 KB 
#include "library.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()

int my_query(vector<int> x, int n) {
  vector<int> m(n, 0);
  for (auto it : x) {
    m[it - 1] = 1;
  }
  return Query(m);
}

void Solve(int n) {
  if (n == 1) {
    Answer({1});
    return;
  }
  vector<vector<int>> g(n + 1);
	vector<vector<int>> segs;
  vector<int> fs = {1}, en = {1};
  segs.pb({1});
  for (int i = 2; i <= n; i++) {
    vector<int> m(n, 0);
    for (int j = 0; j < i; j++) {
      m[j] = 1;
    }
    int rs = Query(m);
    if (rs == SZ(segs) + 1) {
      segs.pb({i});
      fs.pb({i});
      en.pb({i});
      continue;
    }
    else if (rs == SZ(segs)) {
      int l = -1, r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = 0; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) == mid + 1) {
          r = mid;
        }
        else {
          l = mid;
        }
      }
      if (my_query({fs[r], i}, n) == 1) {
        g[fs[r]].pb(i);
        g[i].pb(fs[r]);
        fs[r] = i;
      }
      else {
        g[en[r]].pb(i);
        g[i].pb(en[r]);
        en[r] = i;
      }
      segs[r].pb(i);
    }
    else {
      int l = -1, r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = 0; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) <= mid + 1) {
          r = mid;
        }
        else {
          l = mid;
        } 
      }
      int id1 = r, id2;
      l = r;
      r = SZ(segs) - 1;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        fill(all(m), 0);
        for (int j = id1 + 1; j <= mid; j++) {
          for (auto it : segs[j]) {
            m[it - 1] = 1;
          }
        }
        m[i - 1] = 1;
        if (Query(m) == mid - id1) {
          r = mid;
        }
        else {
          l = mid;
        } 
      }
      id2 = r;
      vector<vector<int>> nsegs;
      vector<int> nfs, nen;
      for (int j = 0; j < SZ(segs); j++) {
        if (j != id1 && j != id2) {
          nsegs.pb(segs[j]);
          nfs.pb(fs[j]);
          nen.pb(en[j]);
        }
      }
      nsegs.pb({i});
      for (auto it : segs[id1]) {
        nsegs.back().pb(it);
      }
      for (auto it : segs[id2]) {
        nsegs.back().pb(it);
      }
      if (my_query({fs[id1], i}, n) == 1) {
        g[i].pb(fs[id1]);
        g[fs[id1]].pb(i);
        nfs.pb(en[id1]);
      }
      else {
        g[i].pb(en[id1]);
        g[en[id1]].pb(i);
        nfs.pb(fs[id1]);
      }
      if (my_query({fs[id2], i}, n) == 1) {
        g[i].pb(fs[id2]);
        g[fs[id2]].pb(i);
        nen.pb(en[id2]);
      }
      else {
        g[i].pb(en[id2]);
        g[en[id2]].pb(i);
        nen.pb(fs[id2]);
      }
      segs = nsegs;
      fs = nfs;
      en = nen;
    }
    /*cerr << i << ' ' << SZ(segs) << endl;
    for (int j = 0; j < SZ(segs); j++) {
      for (auto it : segs[j]) {
        cerr << it << ' ';
      }
      cerr << endl;
    }
    cerr << endl;*/
  }
  int fst = -1;
  for (int i = 1; i <= n; i++) {
    if (SZ(g[i]) == 1) {
      fst = i;
      break;
    }
  }
  assert(fst != -1);
  vector<int> res = {fst};
  int prv = 0, cur = fst;
  for (int i = 1; i < n; i++) {
    for (int nxt : g[cur]) {
      if (nxt != prv) {
        res.pb(nxt);
        prv = cur;
        cur = nxt;
        break;
      }
    }
  }
  assert(SZ(res) == n);
  Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB # of queries: 1272
2 Correct 30 ms 384 KB # of queries: 1257
3 Correct 23 ms 384 KB # of queries: 1321
4 Correct 21 ms 388 KB # of queries: 1329
5 Correct 34 ms 384 KB # of queries: 1319
6 Correct 29 ms 384 KB # of queries: 1315
7 Correct 26 ms 384 KB # of queries: 1327
8 Correct 24 ms 384 KB # of queries: 1249
9 Correct 28 ms 384 KB # of queries: 1331
10 Correct 13 ms 376 KB # of queries: 777
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 2
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 256 KB # of queries: 7
15 Correct 5 ms 256 KB # of queries: 47
16 Correct 6 ms 384 KB # of queries: 110

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB # of queries: 1272
2 Correct 30 ms 384 KB # of queries: 1257
3 Correct 23 ms 384 KB # of queries: 1321
4 Correct 21 ms 388 KB # of queries: 1329
5 Correct 34 ms 384 KB # of queries: 1319
6 Correct 29 ms 384 KB # of queries: 1315
7 Correct 26 ms 384 KB # of queries: 1327
8 Correct 24 ms 384 KB # of queries: 1249
9 Correct 28 ms 384 KB # of queries: 1331
10 Correct 13 ms 376 KB # of queries: 777
11 Correct 4 ms 256 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 2
13 Correct 5 ms 384 KB # of queries: 4
14 Correct 5 ms 256 KB # of queries: 7
15 Correct 5 ms 256 KB # of queries: 47
16 Correct 6 ms 384 KB # of queries: 110
17 Correct 245 ms 384 KB # of queries: 8874
18 Correct 235 ms 508 KB # of queries: 8811
19 Correct 236 ms 504 KB # of queries: 8855
20 Correct 215 ms 384 KB # of queries: 8272
21 Correct 210 ms 384 KB # of queries: 7783
22 Correct 247 ms 384 KB # of queries: 8906
23 Correct 240 ms 384 KB # of queries: 8818
24 Correct 84 ms 384 KB # of queries: 4058
25 Correct 232 ms 384 KB # of queries: 8685
26 Correct 224 ms 384 KB # of queries: 8102
27 Correct 83 ms 384 KB # of queries: 4063
28 Correct 54 ms 384 KB # of queries: 1998
29 Correct 55 ms 384 KB # of queries: 1996
30 Correct 60 ms 384 KB # of queries: 1998