oj.uz

Submission #464245

# Submission time Handle Problem Language Result Execution time Memory
464245 2021-08-12T15:07:06 Z koioi.org-dennisstar Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 50 ms 468 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int> bi[2];

void f(int b, int x, int s, int e) {
	if (s==e) {
		vector<int> v(2);
		v[0]=x, v[1]=bi[b][s];
		if (bi[b].size()==1&&Query(v)!=1) return ;
		adj[x].emplace_back(bi[b][s]);
		adj[bi[b][s]].emplace_back(x);
		return ;
	}
	vector<int> v(1, x), w(1, x);
	int m=(s+e)/2;
	for (int i=s; i<=m; i++) v.emplace_back(bi[b][i]);
	if (Query(v)<v.size()) f(b, x, s, m);
	for (int i=m+1; i<=e; i++) w.emplace_back(bi[b][i]);
	if (Query(w)<w.size()) f(b, x, m+1, e);
}

vector<int> vis; int vc;

void dfs(int i, int b) {
	vis[i]=vc;
	bi[b].emplace_back(i);
	for (auto &j:adj[i]) if (vis[j]!=vc) dfs(j, 1-b);
}

void div(int n) {
	bi[0].clear();
	bi[1].clear();
	vc++;
	for (int i=1; i<=n; i++) if (vis[i]!=vc) dfs(i, 0);
}

void Solve(int n) {
	n*=2;
	adj.resize(n+1);
	vis.resize(n+1);
	for (int i=1; i<=n; i++) {
		for (int j=0; j<2; j++) if (bi[j].size()) f(j, i, 0, bi[j].size()-1);
		div(i);
	}

	auto chk = [&](int x, int y) {
		if (adj[x].size()==1||adj[y].size()==1) return true;
		int f1=0, f2=0;
		vector<int> v(3);
		v[0]=x, v[1]=y;
		for (auto &i:adj[x]) if (i!=y) {
			v[2]=i;
			if (Query(v)==1) { f1=1; break; }
		}
		for (auto &i:adj[y]) if (i!=x) {
			v[2]=i;
			if (Query(v)==1) { f2=1; break; }
		}
		return f1&&f2;
	};
	vector<int> used(n+1);
	for (int i=1; i<=n; i++) if (!used[i]) for (auto &j:adj[i]) if (!used[j]&&i<j&&chk(i, j)) {
		used[i]=used[j]=1;
		Answer(i, j);
		adj[j].clear();
		break;
	}
}

Compilation message

chameleon.cpp: In function 'void f(int, int, int, int)':
chameleon.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  if (Query(v)<v.size()) f(b, x, s, m);
      |      ~~~~~~~~^~~~~~~~~
chameleon.cpp:23:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  if (Query(w)<w.size()) f(b, x, m+1, e);
      |      ~~~~~~~~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 33 ms 344 KB Output is correct
4 Correct 37 ms 468 KB Output is correct
5 Correct 39 ms 352 KB Output is correct
6 Correct 33 ms 352 KB Output is correct
7 Correct 33 ms 356 KB Output is correct
8 Correct 33 ms 328 KB Output is correct
9 Correct 34 ms 352 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Incorrect 50 ms 448 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 33 ms 344 KB Output is correct
4 Correct 37 ms 468 KB Output is correct
5 Correct 39 ms 352 KB Output is correct
6 Correct 33 ms 352 KB Output is correct
7 Correct 33 ms 356 KB Output is correct
8 Correct 33 ms 328 KB Output is correct
9 Correct 34 ms 352 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 0 ms 200 KB Output is correct
14 Correct 0 ms 200 KB Output is correct
15 Correct 0 ms 200 KB Output is correct
16 Correct 0 ms 200 KB Output is correct
17 Correct 1 ms 200 KB Output is correct
18 Correct 0 ms 200 KB Output is correct
19 Correct 2 ms 200 KB Output is correct
20 Correct 1 ms 200 KB Output is correct
21 Correct 1 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 1 ms 200 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 0 ms 200 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Incorrect 50 ms 448 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -