oj.uz

답안 #259873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259873 2020-08-08T18:13:13 Z amoo_safar 카멜레온의 사랑 (JOI20_chameleon) C++14
0 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>

#define pb push_back

#include "chameleon.h"

using namespace std;

const int N = 1e3 + 10;

vector<int> G[N];
vector<int> V[2], P;

int mk[N];
void DFS(int u, int d){
	V[d].pb(u);
	mk[u] = 1;
	for(auto adj : G[u]) if(!mk[adj]) DFS(adj, d ^ 1);
}
int Find(int c, int id){
	int l = 0, r = V[c].size();
	int mid;
	while(l + 1 < r){
		mid = (l + r) >> 1;
		P.clear();
		for(int i = mid; i < (int) V[c].size(); i++) P.pb(V[c][i]);
		P.pb(id);
		if(Query(P) == P.size()) r = mid;
		else l = mid;
	}
	return l;
}
void AddE(int u, int v){
	G[u].pb(v);
	G[v].pb(u);
}
void RemE(int u, int v){
	auto it = G[u].begin();
	while((it != G[u].end()) && (*it != v)) it ++;
	if(it != G[u].end()) G[u].erase(it);

	it = G[v].begin();
	while((it != G[v].end()) && (*it != u)) it ++;
	if(it != G[v].end()) G[v].erase(it);	
}

void Solve(int n){
	for(int i = 1; i <= n + n; i++) G[i].clear();

	for(int i = 1; i <= n + n; i++){
		V[0].clear(); V[1].clear();
		memset(mk, 0, sizeof mk);
		for(int nd = 1; nd < i; nd ++) if(!mk[nd]) DFS(nd, 0);
		for(int it = 0; it < 2; it ++){
			while(true){
				P = V[it];
				P.pb(i);
				if(Query(P) == P.size()) break;
				int res = Find(it, i);
				AddE(i, V[it][res]);		
				V[it].erase(V[it].begin() + res);
			}
		}
	}
	/*
	cerr << "! ";
	for(int i = 1; i <= n + n; i++) cerr << G[i].size() << ' ';
	cerr << '\n';
	*/
	vector< pair<int, int> > ans;
	vector< pair<int, int> > RE;
	for(int i = 1; i <= n + n; i++){
		//assert(G[i].size() != 2);

		int re;
		if(G[i].size() == 3){
			P = {i, G[i][0], G[i][1]};
			if(Query(P) == 1) re = G[i][2];
			else {
				P = {i, G[i][2], G[i][1]};
				if(Query(P) == 1) re = G[i][0];
				else re = G[i][1];
			}
		}
		RE.pb({re, i});
		//cerr << "# " << re << ' ' << i << '\n'; 
	}
	for(auto x : RE) RemE(x.first, x.second);

	while(ans.size() < n){
		int ru = -1, rv = -1;
		for(int i = 1; i <= n + n; i++){
			if(G[i].size() == 1){
				ru = i;
				rv = G[i][0];
				break;
			}
		}

		if(ru != -1){
			ans.pb({ru, rv});
			RemE(ru, rv);
			continue;
		}
		break;
	}
	for(auto x : ans) Answer(x.first, x.second);
}
/*
4
0 0 0 0 1 1 1 1
4 3 2 1 2 3 4 1
6 8 7 5 2 3 4 1

4
1 1 1 0 0 1 0 0
3 1 4 3 1 2 2 4
5 7 4 3 1 8 2 6

4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1

*/

Compilation message

chameleon.cpp: In function 'int Find(int, int)':
chameleon.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(Query(P) == P.size()) r = mid;
      ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(Query(P) == P.size()) break;
        ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size() < n){
        ~~~~~~~~~~~^~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -