oj.uz

Submission #444254

# Submission time Handle Problem Language Result Execution time Memory
444254 2021-07-13T12:43:30 Z kig9981 Chameleon's Love (JOI20_chameleon) C++17
4 / 100
 86 ms 740 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;
		}
		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) {
				E[i].push_back(adj[i][j]);
				E[adj[i][j]].push_back(i);
				break;
			}
		}
		
	}
	for(int i=1;i<=2*N;i++) if(!chk[i]) {
		assert(E[i].size()==2);
		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 74 ms 368 KB Output is correct
4 Correct 78 ms 352 KB Output is correct
5 Correct 75 ms 364 KB Output is correct
6 Correct 78 ms 360 KB Output is correct
7 Correct 79 ms 356 KB Output is correct
8 Correct 81 ms 492 KB Output is correct
9 Correct 86 ms 368 KB Output is correct

Subtask #2
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 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 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 Runtime error 1 ms 584 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
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 1 ms 328 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 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 Runtime error 1 ms 584 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
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 Runtime error 75 ms 740 KB Execution killed with signal 6
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 74 ms 368 KB Output is correct
4 Correct 78 ms 352 KB Output is correct
5 Correct 75 ms 364 KB Output is correct
6 Correct 78 ms 360 KB Output is correct
7 Correct 79 ms 356 KB Output is correct
8 Correct 81 ms 492 KB Output is correct
9 Correct 86 ms 368 KB Output is correct
10 Correct 1 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 0 ms 328 KB Output is correct
14 Correct 1 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 Runtime error 1 ms 584 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -