oj.uz

Submission #448801

# Submission time Handle Problem Language Result Execution time Memory
448801 2021-08-01T15:05:08 Z kimjg1119 Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 59 ms 7792 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

int N;
int color[1010], lk[1010][1010];
vector<int> adj[1010];

int send_query(int t1, int t2, int t3){
	vector<int> tmp;
	tmp.push_back(t1);
	tmp.push_back(t2);
	tmp.push_back(t3);
	return Query(tmp);
}

int vis[1010];
void recolor(int x){
	vis[x] = 1;
	color[x] = 3 - color[x];
	for(int th : adj[x])
		if(!vis[th]) recolor(th);
}

int info(int h, vector<int> &a){
	// check there is an information
	a.push_back(h);
	if(Query(a) == a.size()){
		a.pop_back();
		return -1;
	}
	a.pop_back();
	
	// binary search
	int left = a.size();
	vector<int> chk(left);
	while(left >= 2){
		int mid = left / 2;
		vector<int> v;
		for(int i = 0; i < a.size(); i++){
			if(!chk[i]) v.push_back(a[i]);
			if(v.size() == mid) break;
		}
		
		v.push_back(h);
		int ret = Query(v);
		
		if(ret < mid + 1){
			int cnt = 0;
			for(int i = 0; i < a.size(); i++){
				if(chk[i]) continue;
				if(cnt < mid) cnt++;
				else chk[i] = 1;
			}
			left = mid;
		}
		else{
			int cnt = 0;
			for(int i = 0; i < a.size(); i++){
				if(chk[i]) continue;
				cnt++;
				chk[i] = 1;
				if(cnt == mid) break;
			}
			left = left - mid;
		}
	}
	
	for(int i = 0; i < a.size(); i++){
		if(!chk[i]){
			int ret = a[i];
			/*cout << "A";
			fflush(stdout);*/
			a.erase(a.begin() + i);
			/*cout << "B";
			fflush(stdout);*/
			return ret;
		}
	}
	return -1;
}

int ans_chk[1010];
void find_like(int x){
	if(adj[x].size() == 1){
		// 양방향에 대한 처리
		if(ans_chk[x] || ans_chk[adj[x].back()]) return;
		Answer(x, adj[x].back());
		ans_chk[x] = ans_chk[adj[x].back()] = 1;
	}
	else{
		//assert(adj[x].size() == 3);
		
		int t1 = adj[x][0], t2 = adj[x][1], t3 = adj[x][2];
		int r1 = send_query(x, t1, t2);
		int r2 = send_query(x, t2, t3);
		int r3 = send_query(x, t3, t1);
		
		if(r1 == 1) lk[x][t3] = 1;
		else if(r2 == 1) lk[x][t1] = 1;
		else if(r3 == 1) lk[x][t2] = 1;
	}
}

void Solve(int n){
	N = n * 2;
	
	for(int i = 1; i <= N; i++){
		vector<int> a, b;
		if(!color[i]) color[i] = 1;
		for(int j = 1; j < i; j++)
			if(color[j] == 1) a.push_back(j);
			else if(color[j] == 2) b.push_back(j);
		vector<int> ta, tb;
		while(true){
			int ret = info(i, a);
			if(ret == -1) break;
			ta.push_back(ret);
		}
		while(true){
			int ret = info(i, b);
			if(ret == -1) break;
			tb.push_back(ret);
		}
		
		for(int h : ta){
			if(color[h] == color[i]){
				memset(vis, 0, sizeof(vis));
				recolor(h);
			}
			adj[i].push_back(h);
			adj[h].push_back(i);
		}
		for(int h : tb){
			if(color[h] == color[i]){
				memset(vis, 0, sizeof(vis));
				recolor(h);
			}
			adj[i].push_back(h);
			adj[h].push_back(i);
		}
	}
	
	for(int i=1;i<=N;i++)
		find_like(i);
	
	for(int i = 1; i <= N * 2; i++){
		if(ans_chk[i]) continue;
		for(auto h : adj[i]){
			if(!lk[h][i] && !lk[i][h]){
				Answer(h, i);
				ans_chk[h] = ans_chk[i] = 1;
			}
		}
	}
}

Compilation message

chameleon.cpp: In function 'int info(int, std::vector<int>&)':
chameleon.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if(Query(a) == a.size()){
      |     ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
chameleon.cpp:43:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |    if(v.size() == mid) break;
      |       ~~~~~~~~~^~~~~~
chameleon.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for(int i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
chameleon.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for(int i = 0; i < a.size(); i++){
      |                   ~~^~~~~~~~~~
chameleon.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < a.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 25 ms 396 KB Output is correct
4 Correct 25 ms 328 KB Output is correct
5 Correct 25 ms 328 KB Output is correct
6 Correct 25 ms 392 KB Output is correct
7 Correct 27 ms 408 KB Output is correct
8 Correct 25 ms 396 KB Output is correct
9 Correct 28 ms 388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 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 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 1 ms 712 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 712 KB Output is correct
13 Correct 1 ms 584 KB Output is correct
14 Correct 1 ms 712 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 2 ms 712 KB Output is correct
17 Correct 1 ms 712 KB Output is correct
18 Correct 2 ms 712 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 Runtime error 59 ms 7792 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 328 KB Output is correct
3 Correct 25 ms 396 KB Output is correct
4 Correct 25 ms 328 KB Output is correct
5 Correct 25 ms 328 KB Output is correct
6 Correct 25 ms 392 KB Output is correct
7 Correct 27 ms 408 KB Output is correct
8 Correct 25 ms 396 KB Output is correct
9 Correct 28 ms 388 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 0 ms 328 KB Output is correct
12 Correct 0 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 0 ms 328 KB Output is correct
19 Correct 1 ms 712 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 712 KB Output is correct
22 Correct 1 ms 584 KB Output is correct
23 Correct 1 ms 712 KB Output is correct
24 Correct 1 ms 328 KB Output is correct
25 Correct 2 ms 712 KB Output is correct
26 Correct 1 ms 712 KB Output is correct
27 Correct 2 ms 712 KB Output is correct
28 Correct 0 ms 328 KB Output is correct
29 Correct 0 ms 328 KB Output is correct
30 Runtime error 59 ms 7792 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -