oj.uz

Submission #448726

# Submission time Handle Problem Language Result Execution time Memory
448726 2021-08-01T05:06:56 Z kimjg1119 Chameleon's Love (JOI20_chameleon) C++17
40 / 100
 23 ms 328 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

int N;
int a[101][101], lk[101][101], chk[101];
vector<int> one[101];

int f(int t1, int t2){
	if(t1 == t2) exit(-1);
	if(t1 > t2) swap(t1, t2);
	return a[t1][t2];
}

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);
}

void find_like(int x){
	for(int i = 1; i <= N * 2; i++){
		if(i == x) continue;
		if(f(x, i) == 1) one[x].push_back(i);
	}
	if(one[x].size() == 1){
		// 양방향에 대한 처리
		if(chk[x] || chk[one[x].back()]) return;
		Answer(x, one[x].back());
		chk[x] = chk[one[x].back()] = 1;
	}
	else{
		assert(one[x].size() == 3);
		
		int t1 = one[x][0], t2 = one[x][1], t3 = one[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;
	for(int i = 1; i <= N * 2; i++)
		for(int j = i + 1; j <= N * 2; j++){
			vector<int> v;
			v.push_back(i);
			v.push_back(j);
			a[i][j] = Query(v);
		}
	
	for(int i = 1; i <= N * 2; i++)
		find_like(i);
	
	for(int i = 1; i <= N * 2; i++){
		if(chk[i]) continue;
		for(auto h : one[i]){
			if(!lk[h][i] && !lk[i][h]){
				Answer(h, i);
				chk[h] = chk[i] = 1;
			}
		}
	}
}

Subtask #1
0 / 4.0

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

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 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 200 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 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 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 200 KB Output is correct
8 Correct 0 ms 328 KB Output is correct
9 Correct 0 ms 328 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 2 ms 328 KB Output is correct
13 Correct 2 ms 328 KB Output is correct
14 Correct 2 ms 328 KB Output is correct
15 Correct 2 ms 328 KB Output is correct
16 Correct 2 ms 328 KB Output is correct
17 Correct 2 ms 328 KB Output is correct
18 Correct 2 ms 328 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 0 ms 200 KB Output is correct
3 Incorrect 23 ms 320 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 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Incorrect 23 ms 324 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -