Submission #430812

#	Time	Username	Problem	Language	Result	Execution time	Memory
430812		8e7	Park (JOI17_park)	C++14	20 / 100	1047 ms	1080 KiB

park

#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;
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> chain(vector<int> v) {
	if (v.size() <= 3) return v;
	int piv = v[1 + rand() % (v.size() - 2)];
	vector<int> lef, rig;
	lef.push_back(v[0]), rig.push_back(piv);
	for (int i:v) que[i] = 1;
	que[piv] = 0;
	for (int i = 1;i < v.size() - 1;i++) {
		if (v[i] != piv && query(v[0], v[i])) lef.push_back(v[i]);
		else if (v[i] != piv) rig.push_back(v[i]);
	}
	lef.push_back(piv), rig.push_back(v.back());
	lef = chain(lef), rig = chain(rig);
	vector<int> ret = lef;
	for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
	return ret;
}

void Detect(int T, int N) {
	if (T == 1) {
		for (int i = 0;i < N;i++) {
			for (int j = i + 1;j < N;j++) {
				que[i] = 1, que[j] = 1;
				if (query(i, j)) Answer(i, j);
				que[i] = 0, que[j] = 0;
			}
		}
		return;
	}
	srand(time(NULL));
	vector<int> ini;
	for (int i = 0;i < N;i++) ini.push_back(i);
	ini = chain(ini);
	for (int i = 0;i < N - 1;i++) {
		if (ini[i] > ini[i + 1]) Answer(ini[i + 1], ini[i]);
		else Answer(ini[i], ini[i + 1]);
	}
	//assert(ed.size() == N - 1);
	/*
	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

4
8 7
0 1
0 2
0 3
0 4
0 5
0 6
0 7
*/

Compilation message (stderr)

park.cpp: In function 'std::vector<int> chain(std::vector<int>)':
park.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for (int i = 1;i < v.size() - 1;i++) {
      |                 ~~^~~~~~~~~~~~~~
park.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 1;i < rig.size();i++) ret.push_back(rig[i]);
      |                 ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23