Submission #429670

#TimeUsernameProblemLanguageResultExecution timeMemory
4296708e7Park (JOI17_park)C++14
0 / 100
1158 ms580 KiB
#include "park.h" //Challenge: Accepted #include <iostream> #include <vector> #include <algorithm> #include <utility> #include <random> #include <time.h> #include <assert.h> #include <unordered_map> #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update using namespace std; //using namespace __gnu_pbds; void debug() {cout << endl;} template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);} template <class T> void pary(T l, T r) { while (l != r) {cout << *l << " ";l++;} cout << endl; } #define ll long long #define ld long double #define maxn 1405 #define mod 1000000007 #define pii pair<long long, long long> #define ff first #define ss second static int que[maxn]; vector<pii> ed; int qcnt = 0; void group(vector<int> root, vector<int> nom, int cent); int query(int a, int b) { if (a > b) swap(a, b); if (a == b || (que[a] == 0) || (que[b] == 0)) return 0; qcnt++; return Ask(a, b, que); } vector<int> roots; vector<vector<int> > subs; void solve(vector<int> v) { roots.clear(), subs.clear(); if (v.size() < 2) return; if (v.size() == 2) { ed.push_back({v[0], v[1]}); return; } //debug(v.size()); random_shuffle(v.begin(), v.end()); int cent = v[0]; for (int i = 0;i < maxn;i++) que[i] = 0; for (int i:v) que[i] = 1; if (v.size() > 5) { int num = __lg(v.size()), ma = 0, best = 0, f = 0; for (int i:v) { que[i] = 0; int cnt = 0; for (int j = 0;j < num;j++) { int ix = rand() % v.size(), iy = rand() % v.size(); if (v[ix] == i) ix = (ix + 1) % v.size(); while (iy == ix || v[iy] == i) { iy = (iy + 1) % v.size(); } cnt += query(v[ix], v[iy]) ? 0 : 1; } que[i] = 1; if (cnt > ma) { ma = cnt, best = i; } if (cnt >= (num / 2)) { //debug(7122, i); cent = i, f = 1; break; } } if (!f) cent = best; } //debug(cent); for (int i:v) que[i] = 0; que[cent] = 1; vector<int> adj, sub; for (int i:v) { if (i == cent) continue; que[i] = 1; if (query(i, cent)) { ed.push_back({i, cent}), adj.push_back(i); //debug(49, i, cent); } else { sub.push_back(i); } que[i] = 0; } for (int i:v) que[i] = 1; group(adj, sub, cent); for (int i:v) que[i] = 0; vector<vector<int> > rec; for (int i = 0;i < roots.size();i++) { vector<int> add; add.push_back(roots[i]); for (int j:subs[i]) add.push_back(j); rec.push_back(add); } for (auto i:rec) { solve(i); } } void group(vector<int> root, vector<int> nom, int cent) { if (root.size() == 0) return; if (root.size() == 1) { roots.push_back(root[0]); subs.push_back(nom); return; } vector<int> ar, br, an, bn; for (int i = 0;i < root.size();i++) { if (i < (root.size() / 2)) ar.push_back(root[i]); else br.push_back(root[i]); } for (int i:ar) que[i] = 0; for (int i:nom) { if (!query(i, cent)) { an.push_back(i); } else { bn.push_back(i); } } for (int i:ar) que[i] = 1; group(ar, an, cent), group(br, bn, cent); } void Detect(int T, int N) { srand(time(NULL)); vector<int> ini; for (int i = 0;i < N;i++) ini.push_back(i); solve(ini); //debug(qcnt); for (auto i:ed) { if (i.ff > i.ss) swap(i.ff, i.ss); Answer(i.ff, i.ss); } } /* 4 10 9 0 1 0 2 1 3 2 4 1 5 2 6 2 7 7 8 5 9 */

Compilation message (stderr)

park.cpp: In function 'void solve(std::vector<int>)':
park.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0;i < roots.size();i++) {
      |                 ~~^~~~~~~~~~~~~~
park.cpp: In function 'void group(std::vector<int>, std::vector<int>, int)':
park.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (int i = 0;i < root.size();i++) {
      |                 ~~^~~~~~~~~~~~~
park.cpp:119:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |   if (i < (root.size() / 2)) ar.push_back(root[i]);
      |       ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...