oj.uz

Submission #114705

# Submission time Handle Problem Language Result Execution time Memory
114705 2019-06-02T11:45:12 Z 구사과(#2864) ICC (CEOI16_icc) C++14
100 / 100
 148 ms 772 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;

vector<vector<int>> comp;

bool Q(vector<int> &a, vector<int> &b){
	if(a.empty() || b.empty()) return 0;
	vector<int> va, vb;
	for(auto &i : a){
		for(auto &j : comp[i]){
			va.push_back(j);
		}
	}
	for(auto &i : b){
		for(auto &j : comp[i]){
			vb.push_back(j);
		}
	}
	return query(va.size(), vb.size(), va.data(), vb.data());
}

bool Q2(vector<int> a, vector<int> b){
	if(a.empty() || b.empty()) return 0;
	return query(a.size(), b.size(), a.data(), b.data());
}

int solve(int s, int e, vector<int> &a, vector<int> &b, int d){
	if(d == 0){
		int m = (s+e)/2;
		for(int i=s; i<=m; i++) a.push_back(i);
		for(int i=m+1; i<=e; i++) b.push_back(i);
		return max(m-s+1, e-m);
	}
	int m = (s+e)/2;
	int r1 = solve(s, m, a, b, d-1);
	int r2 = solve(m+1, e, a, b, d-1);
	return max(r1, r2);
}

void make(int s, int e, vector<int> &a, vector<int> &b, int d){
	if(d == 0){
		int m = (s+e)/2;
		for(int i=s; i<=m; i++) a.push_back(i);
		for(int i=m+1; i<=e; i++) b.push_back(i);
		return;
	}
	int m =(s+e)/2;
	vector<int> la, lb;
	solve(s, m, la, lb, d-1);
	if(Q(la, lb)) return make(s, m, a, b, d-1);
	return make(m+1, e, a, b, d-1);
}

int f(int x){
	return x / 2; 
}

pi dnc1(vector<int> a, vector<int> b, int p){
	if(a.size() == 1 && b.size() == 1){
		return pi(a[0], b[0]);
	}
	vector<int> ha1, ha2;
	for(int i=0; i<f(a.size()); i++){
		ha1.push_back(a[i]);
	}
	for(int i=f(a.size()); i<a.size(); i++){
		ha2.push_back(a[i]);
	}
	if(ha2.empty() || Q(ha1, b)) return dnc1(b, ha1, 0);
	return dnc1(b, ha2, 0);
}

pi dnc2(vector<int> a, vector<int> b){
	if(a.size() == 1 && b.size() == 1){
		return pi(a[0], b[0]);
	}
	vector<int> ha1, ha2;
	for(int i=0; i<f(a.size()); i++){
		ha1.push_back(a[i]);
	}
	for(int i=f(a.size()); i<a.size(); i++){
		ha2.push_back(a[i]);
	}
	if(ha2.empty() || Q2(ha1, b)) return dnc2(b, ha1);
	return dnc2(b, ha2);
}

void run(int n) {
	for(int i=1; i<=n; i++){
		vector<int> v = {i};
		comp.push_back(v);
	}
	for(int i=n; i>=2; i--){
		vector<int> a, b;
		int p = 0;
		while(1){
			a.clear();
			b.clear();
			if(solve(0, i-1, a, b, p) == 1) break;
			if(Q(a, b)){
				a.clear();
				b.clear();
				make(0, i-1, a, b, p);
				break;
			}
			p++;
		}
		auto t = dnc1(a, b, 0);
		auto u = dnc2(comp[t.first], comp[t.second]);
		setRoad(u.first, u.second);
		for(auto &i : comp[t.second]){
			comp[t.first].push_back(i);
		}
		comp[t.second].clear();
		for(int j=t.second; j+1<i; j++){
			comp[j] = comp[j+1];
		}
	}
}

Compilation message

icc.cpp: In function 'pi dnc1(std::vector<int>, std::vector<int>, int)':
icc.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=f(a.size()); i<a.size(); i++){
                         ~^~~~~~~~~
icc.cpp: In function 'pi dnc2(std::vector<int>, std::vector<int>)':
icc.cpp:83:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=f(a.size()); i<a.size(); i++){
                         ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Ok! 110 queries used.
2 Correct 8 ms 512 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 512 KB Ok! 617 queries used.
2 Correct 40 ms 640 KB Ok! 636 queries used.
3 Correct 53 ms 512 KB Ok! 675 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 624 KB Ok! 1534 queries used.
2 Correct 119 ms 620 KB Ok! 1639 queries used.
3 Correct 104 ms 576 KB Ok! 1474 queries used.
4 Correct 106 ms 584 KB Ok! 1523 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 576 KB Ok! 1490 queries used.
2 Correct 113 ms 512 KB Ok! 1576 queries used.
3 Correct 109 ms 580 KB Ok! 1501 queries used.
4 Correct 148 ms 704 KB Ok! 1529 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 604 KB Ok! 1501 queries used.
2 Correct 105 ms 512 KB Ok! 1501 queries used.
3 Correct 109 ms 624 KB Ok! 1565 queries used.
4 Correct 108 ms 632 KB Ok! 1501 queries used.
5 Correct 107 ms 620 KB Ok! 1512 queries used.
6 Correct 104 ms 632 KB Ok! 1462 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 772 KB Ok! 1501 queries used.
2 Correct 111 ms 612 KB Ok! 1501 queries used.