oj.uz

Submission #444250

# Submission time Handle Problem Language Result Execution time Memory
444250 2021-07-13T12:40:03 Z kig9981 Chameleon's Love (JOI20_chameleon) C++17
24 / 100
 89 ms 576 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int Query(const std::vector<int> &p);
void Answer(int a, int b);

vector<int> adj[1001], V[2], Q, E[1001];
int P[1001];
bool chk[1001];

void dfs(int c, int v)
{
	V[v].push_back(c);
	chk[c]=true;
	for(auto n: adj[c]) if(!chk[n]) dfs(n,v^1);
}

void check(int v, int l, int r, int i)
{
	if(l>r || adj[i].size()==3) return;
	int s=l, e=r;
	while(s<=e) {
		int m=(s+e)>>1;
		Q.clear(); Q.push_back(i);
		for(int k=l;k<=m;k++) Q.push_back(V[v][k]);
		if(Query(Q)==Q.size()) s=m+1;
		else e=m-1;
	}
	if(s>r) return;
	adj[V[v][s]].push_back(i);
	adj[i].push_back(V[v][s]);
	check(v,s+1,r,i);
}

void Solve(int N)
{
	for(int i=1;i<=2*N;i++) {
		V[0].clear(); V[1].clear();
		for(int j=1;j<i;j++) chk[j]=false;
		for(int j=1;j<i;j++) if(!chk[j]) dfs(j,0);
		check(0,0,V[0].size()-1,i);
		check(1,0,V[1].size()-1,i);
	}
	memset(chk,0,sizeof(chk));
	for(int i=1;i<=2*N;i++) if(!chk[i]) {
		if(adj[i].size()==1) {
			Answer(i,adj[i][0]);
			chk[i]=chk[adj[i][0]]=true;
			continue;
		}
      assert(adj[i].size()==3);
		for(int j=0;j<3;j++) {
			Q.clear(); Q.push_back(i);
			for(int k=0;k<3;k++) if(k^j) Q.push_back(adj[i][k]);
			if(Query(Q)==1) {
				P[i]=adj[i][j];
				break;
			}
		}
		E[i].push_back(P[i]);
		E[P[i]].push_back(i);
	}
	for(int i=1;i<=2*N;i++) if(!chk[i]) {
		for(auto a: adj[i]) {
			bool valid=true;
			for(auto b: E[i]) if(a==b) valid=false;
			if(valid) {
				Answer(i,a);
				chk[i]=chk[a]=true;
				break;
			}
		}
	}
}

Compilation message

chameleon.cpp: In function 'void check(int, int, int, int)':
chameleon.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   if(Query(Q)==Q.size()) s=m+1;
      |      ~~~~~~~~^~~~~~~~~~

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 78 ms 368 KB Output is correct
4 Correct 89 ms 456 KB Output is correct
5 Correct 87 ms 368 KB Output is correct
6 Correct 79 ms 576 KB Output is correct
7 Correct 79 ms 376 KB Output is correct
8 Correct 79 ms 376 KB Output is correct
9 Correct 78 ms 364 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 0 ms 328 KB Output is correct
3 Correct 1 ms 328 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 1 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
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 Correct 1 ms 328 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 1 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 Incorrect 1 ms 328 KB Wrong Answer [5]
13 Halted 0 ms 0 KB -

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 82 ms 392 KB Wrong Answer [5]
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 78 ms 368 KB Output is correct
4 Correct 89 ms 456 KB Output is correct
5 Correct 87 ms 368 KB Output is correct
6 Correct 79 ms 576 KB Output is correct
7 Correct 79 ms 376 KB Output is correct
8 Correct 79 ms 376 KB Output is correct
9 Correct 78 ms 364 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 0 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 0 ms 328 KB Output is correct
15 Correct 0 ms 328 KB Output is correct
16 Correct 1 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 Incorrect 1 ms 328 KB Wrong Answer [5]
22 Halted 0 ms 0 KB -