Submission #922000

#	Time	Username	Problem	Language	Result	Execution time	Memory
922000		Ianis	CONSUL (info1cup19_consul)	C++17	100 / 100	25 ms	428 KiB

consul

#include <vector>
#include <algorithm>
#include <map>
#include <random>
#include <chrono>
#include "grader.h"

using namespace std;

#define fi first
#define se second

#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;

void solve(int n) {
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

   map<int, bool> vis;
   map<int, int> mp;

   for (int i = 1; i <= 55 && i <= n; i++) {
      int pos = abs(int(rng())) % n + 1;
      if (!vis[pos]) {
         vis[pos] = true;
         mp[kth(pos)]++;
      }
   }

   vector<pii> v;
   for (auto [ val, fr ] : mp)
      v.push_back({ -fr, val });
   sort(all(v));

   for (int i = 0; i < 5 && i < int(v.size()); i++) {
      if (cnt(v[i].se) > n / 3) {
         say_answer(v[i].se);
         return;
      }
   }

   say_answer(-1);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 65 / 65