Submission #1193643

#TimeUsernameProblemLanguageResultExecution timeMemory
1193643LucaLucaMThe Big Prize (IOI17_prize)C++20
20 / 100
25 ms1988 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <random> #include "prize.h" std::mt19937 rng(123); std::vector<std::pair<int, int>> memo; int queries = 0; int answer = -1; std::pair<int, int> query(int i) { if (memo[i].first != -1) { return memo[i]; } queries++; assert(queries <= 10000); auto aux = ask(i); if (aux[0] == 0 && aux[1] == 0) { answer = i; } return memo[i] = std::pair<int, int>{aux[0], aux[1]}; } int total_less(int i) { return query(i).first + query(i).second; } int countnonmax; bool is_max(int i) { if (total_less(i) == 0) { answer = i; } return total_less(i) == countnonmax; } int find_best(int n) { memo.resize(n, std::pair<int, int>{-1, -1}); // if (n <= 7) { // for (int i = 0; i < n; i++) { // if (total_less(i) == 0) { // return i; // } // } // } auto get = [&](auto &self, int l, int r, int countLeft) { // countLeft = cate sunt bune in [0, l) if (l == r) { return l; } int mid = (l + r) / 2; int p = mid; while (p >= l && !is_max(p)) { p--; } if (p <= l) { return l; } int st = query(p).first; // std::cout << " ! " << l << ' ' << r << ' ' << p << ' ' << st << '\n'; if (st == countLeft) { if (p != mid) { // stiu sigur ca p + 1 e bun return p + 1; } else { // siu ca in [l..mid] nu e niciunul bun return self(self, mid + 1, r, st); } } else { return self(self, l, p, countLeft); } }; int p1 = rng() % n; int p2 = rng() % n; int p3 = rng() % n; countnonmax = std::max({total_less(p1), total_less(p2), total_less(p3)}); std::vector<int> cand; int l = 0, r = n - 1; while (!is_max(l)) { cand.push_back(l++); } while (!is_max(r)) { cand.push_back(r--); } // stiu ca l si r sunt max while (query(r).first > query(l).first) { int p = get(get, l + 1, r - 1, query(l).first); // std::cout << " ? " << l << ' ' << r << ' ' << p << '\n'; while (!is_max(p)) { cand.push_back(p++); } l = p; } std::sort(cand.begin(), cand.end()); cand.erase(std::unique(cand.begin(), cand.end()), cand.end()); for (int &x : cand) { if (total_less(x) == 0) { return x; } } }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:110:1: warning: control reaches end of non-void function [-Wreturn-type]
  110 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...