oj.uz

답안 #429687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429687 2021-06-16T08:44:24 Z 8e7 Park (JOI17_park) C++14
0 / 100
 1296 ms 580 KB 
#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();
	//pary(v.begin(), v.end());
	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)) {
				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);
		} 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

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 480 KB Output is correct
2 Correct 45 ms 468 KB Output is correct
3 Correct 39 ms 496 KB Output is correct
4 Incorrect 76 ms 456 KB Wrong Answer[6]
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 130 ms 392 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 400 KB Output is correct
2 Correct 169 ms 536 KB Output is correct
3 Correct 152 ms 516 KB Output is correct
4 Correct 113 ms 476 KB Output is correct
5 Correct 118 ms 436 KB Output is correct
6 Correct 88 ms 460 KB Output is correct
7 Correct 94 ms 580 KB Output is correct
8 Correct 116 ms 408 KB Output is correct
9 Incorrect 226 ms 516 KB Wrong Answer[6]
10 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1296 ms 444 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -