oj.uz

Submission #946768

# Submission time Handle Problem Language Result Execution time Memory
946768 2024-03-15T04:28:09 Z siewjh Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 34 ms 596 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
	const int MAXN = 1005;
	vector<int> adj[MAXN];
	int clr[MAXN], ans[MAXN], dest[MAXN], found;
	
	void bs(int l, int r, int x, vector<int> &v){
		if (l > r) return;
		if (found == 3) return;
		vector<int> qv;
		for (int i = l; i <= r; i++) qv.push_back(v[i]);
		qv.push_back(x);
		if (Query(qv) != qv.size()){
			if (l == r){
				adj[x].push_back(v[l]); adj[v[l]].push_back(x);
				found++;
			}
			else{
				int m = (l + r) >> 1;
				bs(l, m, x, v); bs(m + 1, r, x, v);
			}
		}
	}
	
	void dfs(int x, int c){
		clr[x] = c;
		for (int nxt : adj[x])
			if (clr[nxt] == -1)
				dfs(nxt, 1 - c);
	}
}  // namespace

void Solve(int N) {
	vector<int> grps[2];
	for (int i = 1; i <= 2 * N; i++){
		found = 0;
		bs(0, grps[0].size() - 1, i, grps[0]);
		found = 0;
		bs(0, grps[1].size() - 1, i, grps[1]);
		memset(clr, -1, sizeof(clr));
		for (int j = 1; j <= i; j++)
			if (clr[j] == -1)
				dfs(j, 0);
		grps[0].clear(); grps[1].clear();
		for (int j = 1; j <= i; j++) grps[clr[j]].push_back(j);
	}
	memset(dest, -1, sizeof(dest));
	for (int i = 1; i <= 2 * N; i++){
		if (adj[i].size() == 1) ans[i] = adj[i][0];
		else{
			for (int k = 0; k <= 2; k++){
				vector<int> qvec; qvec.push_back(i);
				for (int ind = 0; ind <= 2; ind++)
					if (ind != k)
						qvec.push_back(adj[i][ind]);
				if (Query(qvec) == 1){
					dest[i] = adj[i][k];
					break;
				}
			}
		}
	}
	for (int i = 1; i <= 2 * N; i++){
		if (adj[i].size() == 1) continue;
		for (int k = 0; k <= 2; k++)
			if (adj[i][k] != dest[i] && dest[adj[i][k]] != i){
				ans[i] = adj[i][k];
				break;
			}
	}
	for (int i = 1; i <= 2 * N; i++)
		if (ans[i] > i)
			Answer(i, ans[i]);
}

Compilation message

chameleon.cpp: In function 'void {anonymous}::bs(int, int, int, std::vector<int>&)':
chameleon.cpp:16:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   if (Query(qv) != qv.size()){
      |       ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 17 ms 504 KB Output is correct
4 Correct 17 ms 344 KB Output is correct
5 Correct 17 ms 488 KB Output is correct
6 Correct 18 ms 344 KB Output is correct
7 Correct 17 ms 344 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 17 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

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