oj.uz

Submission #429585

# Submission time Handle Problem Language Result Execution time Memory
429585 2021-06-16T07:18:57 Z Kevin_Zhang_TW Park (JOI17_park) C++17
20 / 100
 275 ms 700 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "park.h"

const int MAX_N = 1400;
static int Place[1400];

int n;

int mrand(int l, int r) {
	static random_device rd;
	static mt19937 gen(rd());
	return uniform_int_distribution(l, r)(gen);
}

int qry_list(int a, int b, vector<int> go) {
	static int ok[MAX_N];
	fill(ok, ok + n, 0);
	for (int i : go) ok[i] = true;
	ok[a] = ok[b] = true;
	return Ask(a, b, ok);
}
int qry_tf(int a, int b, vector<int> go) {
	static int ok[MAX_N];
	copy(AI(go), ok);
	return Ask(a, b, ok);
}

void ans(int a, int b) {
	if (a > b) swap(a, b);
	Answer(a, b);
}

vector<int> find_path(int a, int b) {
	vector<int> onpath(n, true);
	for (int i = 0;i < n;++i) if (i != a && i != b) {
		onpath[i] = false;
		if (!qry_tf(a, b, onpath)) onpath[i] = true;
	}
	vector<int> path;
	for (int i = 0;i < n;++i) if (i != a && i != b && onpath[i])
		path.pb(i);

	function<void(int, int)> qst = [&](int l, int r) {
		if (r-l+1 <= 1) return;
		int p = mrand(l, r);
		vector<int> lhs, rhs;

		onpath[ path[p] ] = false;

		for (int i = l;i <= r;++i) if (i != p) {
			if (qry_tf(a, path[i], onpath))
				lhs.pb(path[i]);
			else
				rhs.pb(path[i]);
		}

		onpath[ path[p] ] = true;

		int np = lhs.size();

		lhs.pb(path[p]);
		lhs.insert(end(lhs), AI(rhs));
		for (int i = 0, j = l;i < lhs.size();++i) {
			path[j++] = lhs[i];
		}

		qst(l, l + np-1);
		qst(l+np+1, r);
	};

	qst(0, (int) path.size() - 1);

	path.insert(begin(path), a);
	path.insert(end(path), b);

	return path;
}
void Detect(int T, int N) {
	n = N;

	if (T == 1) {
		for (int i = 0;i < n;++i)
			for (int j = i+1;j < n;++j)
				if (qry_list(i, j, {i, j}))
					ans(i, j);
		return;
	}

	if (T == 2) {
		auto a = find_path(0, N-1);

		for (int i = 1;i < N;++i)
			ans(a[i-1], a[i]);
		return;
	}

}

Compilation message

park.cpp: In lambda function:
park.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (int i = 0, j = l;i < lhs.size();++i) {
      |                         ~~^~~~~~~~~~~~
park.cpp: At global scope:
park.cpp:20:12: warning: 'Place' defined but not used [-Wunused-variable]
   20 | static int Place[1400];
      |            ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 9 ms 328 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 11 ms 332 KB Output is correct
5 Correct 10 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 700 KB Output is correct
2 Correct 111 ms 612 KB Output is correct
3 Correct 111 ms 468 KB Output is correct
4 Correct 233 ms 616 KB Output is correct
5 Correct 258 ms 464 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -