oj.uz

Submission #1020287

# Submission time Handle Problem Language Result Execution time Memory
1020287 2024-07-11T19:40:49 Z ttamx Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 42 ms 544 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

void Solve(int n){
	auto bsearch=[&](vector<int> &a,int st,int u){
		int l=st,r=a.size();
		while(l<r){
			int m=(l+r)/2;
			vector<int> b{u};
			for(int i=st;i<=m;i++)b.emplace_back(a[i]);
			if(Query(b)<b.size())r=m;
			else l=m+1;
		}
		return l;
	};
	vector<vector<int>> adj(2*n+1);
	for(int i=2;i<=2*n;i++){
		vector<int> col(i);
		function<void(int,int)> dfs=[&](int u,int c){
			if(col[u])return;
			col[u]=c;
			for(auto v:adj[u])dfs(v,3-c);
		};
		for(int j=1;j<i;j++)dfs(j,1);
		vector<int> comp[2];
		for(int j=1;j<i;j++)comp[col[j]-1].emplace_back(j);
		for(int j=0;j<2;j++){
			int st=0;
			while((st=bsearch(comp[j],st,i))<comp[j].size()){
				int u=comp[j][st];
				adj[i].emplace_back(u);
				adj[u].emplace_back(i);
				st++;
			}
		}
	}
	vector<int> ans(2*n+1),val(2*n+1);
	for(int i=1;i<=2*n;i++){
		if(adj[i].size()==1){
			ans[i]=adj[i][0];
			ans[adj[i][0]]=i;
		}else{
			for(auto x:adj[i])val[i]^=x;
			while(Query({i,adj[i][0],adj[i][1]})>1){
				rotate(adj[i].begin(),adj[i].begin()+1,adj[i].end());
			}
			val[i]^=adj[i][2];
			val[adj[i][2]]^=i;
		}
	}
	for(int i=1;i<=2*n;i++){
		if(!ans[i])ans[i]=val[i];
		if(i<ans[i])Answer(i,ans[i]);
	}
}

Compilation message

chameleon.cpp: In lambda function:
chameleon.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |    if(Query(b)<b.size())r=m;
      |       ~~~~~~~~^~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:31:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    while((st=bsearch(comp[j],st,i))<comp[j].size()){
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 36 ms 480 KB Output is correct
4 Correct 36 ms 528 KB Output is correct
5 Correct 42 ms 344 KB Output is correct
6 Correct 36 ms 344 KB Output is correct
7 Correct 36 ms 344 KB Output is correct
8 Correct 36 ms 340 KB Output is correct
9 Correct 36 ms 532 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 39 ms 544 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 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 36 ms 480 KB Output is correct
4 Correct 36 ms 528 KB Output is correct
5 Correct 42 ms 344 KB Output is correct
6 Correct 36 ms 344 KB Output is correct
7 Correct 36 ms 344 KB Output is correct
8 Correct 36 ms 340 KB Output is correct
9 Correct 36 ms 532 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Incorrect 39 ms 544 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -