Submission #779534

#TimeUsernameProblemLanguageResultExecution timeMemory
779534sadsaXylophone (JOI18_xylophone)C++17
47 / 100
268 ms98612 KiB
#include "xylophone.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using ii = tuple<int, int>; using vii = vector<ii>; constexpr int iINF = numeric_limits<int>::max(); constexpr ll lINF = numeric_limits<ll>::max(); template <typename T> void DBG(T&& arg) { cerr << arg << '\n'; } template <typename T, typename... Ts> void DBG(T&& x, Ts&&... y) { cerr << x << ' '; DBG(y...); } static vector<vi> qcache; int queries; int q(int l, int r) { if (l > r) swap(l, r); int Q; if (l == r) Q = 0; else { if (qcache[l][r] == -1) queries++; Q = (qcache[l][r] != -1)? qcache[l][r]: (qcache[l][r] = query(l, r)); } DBG("query:", l, r, "V:", Q); return Q; } int find_1(int N) { DBG("find_1====================="); int l = 1; int r = N-1; int target = N-1; while (l != r) { DBG("l,r", l, r); int mid = (l + r + 1) / 2; DBG("mid", mid); if (q(mid, N) == target) { l = mid; } else { r = mid-1; } } return l; } // finds a2 int get_next(int a0, int a1, int q02, int q12) { int a2; int q01 = abs(a1 - a0); if (q01 == q02) { DBG("WOOF"); // minmax didnt change => ai2 between ai0 and ai1 if (a0 < a1) a2 = a1 - q12; else a2 = a1 + q12; } else { DBG("MIAUW"); if (a0 < a1) { if (q12 >= q02) a2 = a1 - q12; else a2 = a1 + q12; } else { if (q12 == q02) a2 = a1 + q12; else if (q12 < q02) a2 = a1 - q12; else a2 = a1 + q12; } } return a2; } void solve(int N) { qcache.clear(); qcache.resize(N+1, vi(N+1, -1)); queries = 0; int index1 = find_1(N); DBG("index 1:", index1); //int indexN = find_N(index1, N); //DBG("index N:", indexN); vi ans(N+1); ans[index1] = 1; ans[index1+1] = 1+q(index1, index1+1); bitset<5001> found; found[1] = 1; found[ans[index1+1]] = 1; for (int i = index1; i+2 <= N && found.count() < N-1; ++i) { DBG("starti", i); int i0=i; int i1=i+1; int i2=i+2; int q02 = q(i0, i2); int q12 = q(i1, i2); ans[i2] = get_next(ans[i0], ans[i1], q02, q12); found[ans[i2]] = 1; DBG("next guess", ans[i0], ans[i1], ans[i2]); DBG("with info", q02, q12); } for (int i = index1+1; i-2 > 0 && found.count() < N-1; --i) { int i0 = i; int i1 = i-1; int i2 = i-2; int q02 = q(i2, i); int q12 = q(i2, i1); ans[i2] = get_next(ans[i0], ans[i1], q02, q12); found[ans[i2]] = 1; } if (found.count() == N-1) { int missing_a; for (int i = 1; i <= N; ++i) { if (!found[i]) { missing_a = i; break; } } *find(ans.begin()+1, ans.end(), 0) = missing_a; } DBG(queries); for (int i = 1; i <= N; ++i) { answer(i, ans[i]); } }

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:110:49: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |  for (int i = index1; i+2 <= N && found.count() < N-1; ++i) {
      |                                   ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:125:50: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |  for (int i = index1+1; i-2 > 0 && found.count() < N-1; --i) {
      |                                    ~~~~~~~~~~~~~~^~~~~
xylophone.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |  if (found.count() == N-1) {
      |      ~~~~~~~~~~~~~~^~~~~~
xylophone.cpp:145:38: warning: 'missing_a' may be used uninitialized in this function [-Wmaybe-uninitialized]
  145 |   *find(ans.begin()+1, ans.end(), 0) = missing_a;
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...