Submission #952709

#TimeUsernameProblemLanguageResultExecution timeMemory
952709kilkuwuLibrary (JOI18_library)C++11
0 / 100
16 ms696 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "library.h" #else #include <vector> int Query(const std::vector<int>& M); void Answer(const std::vector<int>& res); #endif void Solve(int N) { std::vector<int> dp(N + 1, -1); auto get_pref = [&](int x) { if (dp[x] != -1) return dp[x]; std::vector<int> a(N); for (int i = 0; i < x; i++) { a[i] = 1; } return dp[x] = Query(a); }; auto get_pref_more = [&](int x, int y) { std::vector<int> a(N); a[y - 1] = 1; for (int i = 0; i < x; i++) { a[i] = 1; } return Query(a); }; std::vector<std::vector<int>> adj(N + 1); dp[1] = 1; for (int i = 2; i <= N; i++) { if (get_pref(i) - get_pref(i - 1) == 1) { continue; } if (get_pref(i) - get_pref(i - 1) == 0) { int lb = 1, rb = i - 1; while (lb < rb) { int mid = (lb + rb) / 2; int bef = get_pref(mid); int aft = get_pref_more(mid, i); if (aft - bef == 0) { rb = mid; } else { lb = mid + 1; } } adj[rb].push_back(i); adj[i].push_back(rb); continue; } assert(get_pref(i) - get_pref(i - 1) == -1); int lb = 1, rb = i - 1; while (lb < rb) { int mid = (lb + rb) / 2; int bef = get_pref(mid); int aft = get_pref_more(mid, i); if (aft - bef == -1) { // now we can be sure rb = mid; } else { lb = mid + 1; } } int z = rb; adj[z].push_back(i); adj[i].push_back(z); lb = 1, rb = z - 1; // z - 1 while (lb < rb) { int mid = (lb + rb) / 2; int bef = get_pref(mid); int aft = get_pref_more(mid, i); if (aft - bef == 0) { rb = mid; } else { lb = mid + 1; } } adj[rb].push_back(i); adj[i].push_back(rb); } std::vector<int> res; std::function<void(int, int)> dfs = [&](int u, int p) { res.push_back(u); for (int v : adj[u]) { if (v == p) continue; dfs(v, u); } }; for (int i = 1; i <= N; i++) { if ((int) adj[i].size() == 1) { dfs(i, i); break; } } assert(res.size() == N); Answer(res); }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from library.cpp:1:
library.cpp: In function 'void Solve(int)':
library.cpp:113:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |   assert(res.size() == N);
      |          ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...