oj.uz

Submission #470445

# Submission time Handle Problem Language Result Execution time Memory
470445 2021-09-03T19:26:51 Z Namnamseo Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 44 ms 448 KB 
#include "chameleon.h"
#include <utility>
#include <vector>
using namespace std;
using vi=vector<int>;
using pp=pair<int,int>;
using pvi=pair<vi,vi>;
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(t) ((int)((t).size()))
const int maxn2 = int(1e3) + 10;

int n;

vector<pvi> v;
vi graph[maxn2];

bool Search(int i, vi &v, int l, int r) {
	if (l == r) return false;
	vi qry(v.begin()+l, v.begin()+r);
	qry.push_back(i);
	int qres = Query(qry);
	if (qres == sz(qry)) return false;
	if (l+1 == r) {
		int j = v[l];
		graph[i].pb(j); graph[j].pb(i);
		return true;
	}
	int md = (l+r)/2;
	Search(i, v, l, md);
	Search(i, v, md, r);
	return true;
}

void Rebuild(int p) {
	static bool vis[maxn2], col[maxn2];
	fill(vis+1, vis+p+1, 0);
	fill(col+1, col+p+1, 0);
	int vs = 0;
	for (int i=1; i<=p; ++i) if (!vis[i]) {
		static int q[maxn2], hd, tl;
		hd = 0; tl = 1; q[0] = i; vis[i] = true;
		if (sz(v) <= vs) v.resize(vs+1);
		v[vs].first.clear();
		v[vs].second.clear();
		while (hd < tl) {
			int x = q[hd++];
			(col[x]?v[vs].second:v[vs].first).push_back(x);
			for (int y:graph[x]) if (!vis[y]) {
				vis[y] = true;
				col[y] = !col[x];
				q[tl++] = y;
			}
		}
		++vs;
	}
	v.resize(vs);
}

void Solve(int N_) {
	n = N_;
	for (int i=1; i<=2*n; ++i) {
		static vi lefts, rights;
		lefts.clear(); rights.clear();
		for (auto &tmp : v) {
			lefts.insert(lefts.end(), all(tmp.first));
			rights.insert(rights.end(), all(tmp.second));
		}
		bool found = Search(i, lefts, 0, sz(lefts));
		found = Search(i, rights, 0, sz(rights)) || found;
		if (!found) v.push_back({{i}, {}});
		else Rebuild(i);
	}

	static bool is_directed[maxn2][maxn2];
	for (int i=1; i<=2*n; ++i) {
		if (sz(graph[i]) == 1) continue;
		int a = graph[i][0], b = graph[i][1], c = graph[i][2];
		int my_out = -1;
		if (Query(vi{i, a, b}) == 1) my_out = c; else
		if (Query(vi{i, b, c}) == 1) my_out = a; else
		if (Query(vi{i, c, a}) == 1) my_out = b;
		is_directed[i][my_out] = true;
		is_directed[my_out][i] = true;
	}
	for (int i=1; i<=2*n; ++i) for (int j:graph[i]) {
		if (i<j && !is_directed[i][j]) {
			Answer(i, j);
		}
	}
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 33 ms 432 KB Output is correct
4 Correct 32 ms 328 KB Output is correct
5 Correct 32 ms 428 KB Output is correct
6 Correct 32 ms 328 KB Output is correct
7 Correct 32 ms 432 KB Output is correct
8 Correct 32 ms 448 KB Output is correct
9 Correct 32 ms 328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 0 ms 328 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 0 ms 328 KB Output is correct
6 Correct 0 ms 328 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 328 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Incorrect 44 ms 428 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 33 ms 432 KB Output is correct
4 Correct 32 ms 328 KB Output is correct
5 Correct 32 ms 428 KB Output is correct
6 Correct 32 ms 328 KB Output is correct
7 Correct 32 ms 432 KB Output is correct
8 Correct 32 ms 448 KB Output is correct
9 Correct 32 ms 328 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 0 ms 328 KB Output is correct
13 Correct 0 ms 328 KB Output is correct
14 Correct 0 ms 328 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 0 ms 328 KB Output is correct
17 Correct 0 ms 328 KB Output is correct
18 Correct 0 ms 328 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 1 ms 328 KB Output is correct
23 Correct 1 ms 328 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 1 ms 328 KB Output is correct
26 Correct 1 ms 328 KB Output is correct
27 Correct 1 ms 328 KB Output is correct
28 Correct 0 ms 328 KB Output is correct
29 Correct 0 ms 328 KB Output is correct
30 Incorrect 44 ms 428 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -