이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pii pair<int, int>
#define f first
#define s second
#define sz(x) (int)((x).size())
const int siz = 1e6+40;
int nbE;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int caller(vector<int> where) {
vector<signed> u(nbE, 0);
for (int i : where) {
u[i] = 1; // se heavy
}
int r = ask(u);
return r;
}
int twoP(vector<int> part, vector<signed> edgeX, vector<signed> edgeY) {
set<int> se;
for (int i : part) {
se.insert(i);
}
vi where;
for (int i = 0; i < nbE; i++) {
int u = se.count(edgeX[i]);
int v = se.count(edgeY[i]);
if ((u^v) == 1) {
where.push_back(i);
}
}
return caller(where);
}
void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) {
nbE = sz(edgeX);
int distVert = caller({});
vi part [2];
while (1) {
part[0] = part[1] = {};
for (int i = 0; i < n; i++) {
if (rng()%2) {
part[0].push_back(i);
} else {
part[1].push_back(i);
}
}
int r = twoP(part[0], edgeX, edgeY);
if (r%2 != distVert%2) {
break;
}
}
for (int i = 0; i < 2; i++) {
while (sz(part[i]) != 1) {
assert(!part[i].empty());
vi lp, rp;
for (int j : part[i]) {
if (sz(lp) <= sz(rp)) {
lp.push_back(j);
} else {
rp.push_back(j);
}
}
int r = twoP(lp, edgeX, edgeY);
if (r%2 != distVert%2) {
part[i] = lp;
} else {
part[i] = rp;
}
}
}
int ansX = part[0][0];
int ansY = part[1][0];
answer(ansX, ansY);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |