oj.uz

Submission #43982

# Submission time Handle Problem Language Result Execution time Memory
43982 2018-03-29T03:47:20 Z azneye Library (JOI18_library) C++17
100 / 100
 703 ms 60348 KB 
#include <bits/stdc++.h>
#include "library.h"

using namespace std;

namespace {
#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define VERA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int ll;

void DFS(const vector<vector<ll>>& adj, ll at, vector<bool>& vis, vector<ll>& res) {
  if (vis[at])
    return;
  res.push_back(at);
  vis[at] = true;
  VERA(to, adj[at]) {
    DFS(adj, to, vis, res);
  }
}

map<vector<ll>, ll> cache;

ll MyQuery(const vector<ll>& ques) {
  if (count(ALL(ques), 1) == 0) return 0;
  auto it = cache.find(ques);
  if (it == cache.end()) {
    const ll res = Query(ques);
    cache.emplace(ques, res);
    return res;
  } else {
    return it->second;
  }
}

}

void Solve(int N) {
  if (N == 1) {
    Answer({1});
    return;
  }
  vector<vector<ll>> adj(N);
  vector<ll> ques(N);
  set<ll> ends;
  VEVE(k, 0, N) {
    if (SIZE(adj[k]) == 2)
      continue;
    if (SIZE(ends) < 2) {
      fill(ALL(ques), 1);
      ques[k] = 0;
      if (MyQuery(ques) == 1) {
        ends.insert(k);
        if (SIZE(adj[k]) == 1)
          continue;
      }
    }
    while (SIZE(adj[k]) < 2 - ends.count(k)) {
      ll low = 0, hig = N - 1;
      while (low < hig) {
        const ll mid = (low + hig) / 2;
        // is k adjacent to book in [low,mid]?
        fill(ALL(ques), 0);
        VEVE(i, low, mid + 1) ques[i] = 1;
        VERA(to, adj[k]) ques[to] = 0;
        ques[k] = 0;
        const ll cnt_without = MyQuery(ques);
        ques[k] = 1;
        const ll cnt_with = MyQuery(ques);
        if (cnt_with <= cnt_without) {
          hig = mid;
        } else {
          low = mid + 1;
        }
      }
//      DEBUG(k + 1, hig + 1);
      adj[k].push_back(hig);
      adj[hig].push_back(k);
    }
  }
  vector<ll> res;
  vector<bool> vis(N, false);
  VEVE(v, 0, N) if (SIZE(adj[v]) == 1) {
      DFS(adj, v, vis, res);
      break;
    }
  VERA(r, res) ++r;
//  DEBUG(res);
  Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:61:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (SIZE(adj[k]) < 2 - ends.count(k)) {
                         ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1700 KB Output is correct
2 Correct 36 ms 1848 KB Output is correct
3 Correct 38 ms 1920 KB Output is correct
4 Correct 38 ms 1924 KB Output is correct
5 Correct 35 ms 1968 KB Output is correct
6 Correct 36 ms 1992 KB Output is correct
7 Correct 39 ms 1992 KB Output is correct
8 Correct 37 ms 1992 KB Output is correct
9 Correct 37 ms 2040 KB Output is correct
10 Correct 20 ms 2040 KB Output is correct
11 Correct 2 ms 2040 KB Output is correct
12 Correct 2 ms 2040 KB Output is correct
13 Correct 2 ms 2040 KB Output is correct
14 Correct 2 ms 2040 KB Output is correct
15 Correct 2 ms 2040 KB Output is correct
16 Correct 4 ms 2040 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1700 KB Output is correct
2 Correct 36 ms 1848 KB Output is correct
3 Correct 38 ms 1920 KB Output is correct
4 Correct 38 ms 1924 KB Output is correct
5 Correct 35 ms 1968 KB Output is correct
6 Correct 36 ms 1992 KB Output is correct
7 Correct 39 ms 1992 KB Output is correct
8 Correct 37 ms 1992 KB Output is correct
9 Correct 37 ms 2040 KB Output is correct
10 Correct 20 ms 2040 KB Output is correct
11 Correct 2 ms 2040 KB Output is correct
12 Correct 2 ms 2040 KB Output is correct
13 Correct 2 ms 2040 KB Output is correct
14 Correct 2 ms 2040 KB Output is correct
15 Correct 2 ms 2040 KB Output is correct
16 Correct 4 ms 2040 KB Output is correct
17 Correct 574 ms 46604 KB Output is correct
18 Correct 541 ms 46604 KB Output is correct
19 Correct 583 ms 46604 KB Output is correct
20 Correct 511 ms 46604 KB Output is correct
21 Correct 452 ms 46604 KB Output is correct
22 Correct 548 ms 46604 KB Output is correct
23 Correct 555 ms 46604 KB Output is correct
24 Correct 170 ms 46604 KB Output is correct
25 Correct 540 ms 46604 KB Output is correct
26 Correct 499 ms 46604 KB Output is correct
27 Correct 167 ms 46604 KB Output is correct
28 Correct 703 ms 60240 KB Output is correct
29 Correct 690 ms 60348 KB Output is correct
30 Correct 695 ms 60348 KB Output is correct