oj.uz

답안 #1010841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010841 2024-06-29T12:25:36 Z LCJLY 카멜레온의 사랑 (JOI20_chameleon) C++14
44 / 100
 65 ms 512 KB 
#include "chameleon.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
	
//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,3>pi2;

//Query(vector<int>)
//Answer(int,int)

vector<int>adj[1005];
bool color[1005];
bool visited[1005];

void dfs(int index){
	visited[index]=true;
	//show(visit,index);
	for(auto it:adj[index]){
		if(visited[it]) continue;
		color[it]=color[index]^1;
		dfs(it);
	}
}

pii f(int a, int b){
	return {min(a,b),max(a,b)};
}

void Solve(int n){
	for(int x=1;x<=2*n;x++){
		memset(color,0,sizeof(color));
		memset(visited,0,sizeof(visited));
		for(int y=1;y<x;y++){
			if(!visited[y]){
				dfs(y);
			}
		}
		
		//for(int y=1;y<=x;y++){
			//cout << color[y] << " ";
		//}
		//cout << endl;
		
		vector<int>v[2];
		for(int y=1;y<x;y++){
			v[color[y]].push_back(y);
		}
		
		for(int i=0;i<2;i++){
			//identify all pairs
			int last=0;
			for(int j=0;j<3;j++){
				int l=last;
				int r=v[i].size()-1;
				int best=r+1;
				int mid;
				while(l<=r){
					mid=(l+r)/2;
					vector<int>storage;
					for(int k=last;k<=mid;k++){
						storage.push_back(v[i][k]);
					}
					storage.push_back(x);
					int hold=Query(storage);
					if(hold!=(int)storage.size()){
						best=mid;
						r=mid-1;
					}
					else l=mid+1;
				}
				if(best==(int)v[i].size()) break;
				last=best+1;
				//show3(edgea,x,edgeb,v[i][best],i,i);
				adj[x].push_back(v[i][best]);
				adj[v[i][best]].push_back(x);
			}
		}
	}
	
	map<pii,int>mp;
	
	for(int x=1;x<=2*n;x++){
		if(adj[x].size()==1){
			mp[f(x,adj[x][0])]++;
		}
		else if(adj[x].size()==3){
			int hold=Query({x,adj[x][0],adj[x][1]});
			int hold2=Query({x,adj[x][0],adj[x][2]});
			if(hold==1){
				mp[f(x,adj[x][0])]++;
				mp[f(x,adj[x][1])]++;
			}
			else if(hold2==1){
				mp[f(x,adj[x][0])]++;
				mp[f(x,adj[x][2])]++;
			}
			else{
				mp[f(x,adj[x][1])]++;
				mp[f(x,adj[x][2])]++;
			}
		}
	}
	
	for(auto it:mp){
		if(it.second==2){
			//show2(a,it.first.first,b,it.first.second);
			Answer(it.first.first,it.first.second);
		}
	}
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 44 ms 344 KB Output is correct
4 Correct 50 ms 492 KB Output is correct
5 Correct 37 ms 492 KB Output is correct
6 Correct 65 ms 344 KB Output is correct
7 Correct 37 ms 496 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 37 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 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 2 ms 344 KB Output is correct
13 Correct 2 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 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 45 ms 344 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 44 ms 344 KB Output is correct
4 Correct 50 ms 492 KB Output is correct
5 Correct 37 ms 492 KB Output is correct
6 Correct 65 ms 344 KB Output is correct
7 Correct 37 ms 496 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 37 ms 344 KB Output is correct
10 Correct 1 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 1 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 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 2 ms 344 KB Output is correct
22 Correct 2 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 1 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 0 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Incorrect 45 ms 344 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -