oj.uz

답안 #210724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210724 2020-03-18T07:06:59 Z bensonlzl CEOI16_icc (CEOI16_icc) C++14
100 / 100
 176 ms 616 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int,int> pi;

int s0, s1, a[105], b[105];

int par[105];
vector<int> sz[105];
int cnt[8], setbit;

void res(){
	for (int i = 0; i < 105; ++i){
		a[i] = b[i] = 0;
	}
	s0 = s1 = 0;
}

int query_v(vector<int> A, vector<int> B){
	res();
	for (int i = 0; i < A.size(); ++i){
		a[i] = A[i];
	}
	for (int i = 0; i < B.size(); ++i){
		b[i] = B[i];
	}
	return query(A.size(),B.size(),a,b);
}

pi solve(vector<int> A, vector<int> B){
	//cerr << A.size() << ' ' << B.size() << '\n';
	if (B.size() == 1){
		if (A.size() == 1){
			return pi(A[0],B[0]);
		}
		else return solve(B,A);
	}
	vector<int> b0, b1;
	for (int i = 0; i < B.size(); ++i){
		if (i%2 == 0) b0.push_back(B[i]);
		else b1.push_back(B[i]);
	}
	int q = query_v(A,b0);
	if (q) return solve(A,b0);
	else return solve(A,b1);
}

int find_par(int x){
	if (par[x] != x) par[x] = find_par(par[x]);
	return par[x];
}

void merg(int x, int y){
	int X = find_par(x), Y = find_par(y);
	if (X == Y) return;
	if (sz[X].size() < sz[Y].size()) swap(X,Y);
	for (auto it : sz[Y]){
		sz[X].push_back(it);
	}
	par[Y] = X;
}

vector<int> expand(vector<int> p){
	vector<int> r;
	for (auto it : p){
		for (auto it2 : sz[it]){
			r.push_back(it2);
		}
	}
	return r;
}



void run(int n) {
	for (int i = 1; i <= n; ++i){
		par[i] = i;
		sz[i].push_back(i);
	}
    for (int i = 1; i < n; ++i){
    	vector<int> pars;
    	for (int k = 1; k <= n; ++k){
    		pars.push_back(find_par(k));
    	}
    	
    	sort(pars.begin(),pars.end());
    	pars.resize(unique(pars.begin(),pars.end())-pars.begin());
    	shuffle(pars.begin(),pars.end(),rng);
    	vector<int> v0, v1, ax, bx;
    	int check = 0;
    	for (int b = 0; b < 6; ++b){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << b)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    		int q = query_v(ax,bx);
    		//cerr << b << ' ' << q << '\n';
    		if (q){
    			check = 1;
    			break;
    		}
    		
    	}
    	if (!check){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << 6)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    	}
    	pi X = solve(ax,bx);
    	//cerr << X.first << ' ' << X.second << '\n';
    	setRoad(X.first,X.second);
    	merg(X.first,X.second);
    }
}

Compilation message

icc.cpp: In function 'int query_v(std::vector<int>, std::vector<int>)':
icc.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'pi solve(std::vector<int>, std::vector<int>)':
icc.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:99:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~
icc.cpp:118:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 504 KB Ok! 106 queries used.
2 Correct 11 ms 508 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 504 KB Ok! 524 queries used.
2 Correct 53 ms 504 KB Ok! 642 queries used.
3 Correct 51 ms 504 KB Ok! 633 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 504 KB Ok! 1403 queries used.
2 Correct 176 ms 552 KB Ok! 1577 queries used.
3 Correct 143 ms 504 KB Ok! 1402 queries used.
4 Correct 150 ms 504 KB Ok! 1485 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 504 KB Ok! 1499 queries used.
2 Correct 161 ms 584 KB Ok! 1490 queries used.
3 Correct 165 ms 504 KB Ok! 1570 queries used.
4 Correct 143 ms 504 KB Ok! 1436 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 504 KB Ok! 1547 queries used.
2 Correct 172 ms 504 KB Ok! 1538 queries used.
3 Correct 172 ms 504 KB Ok! 1589 queries used.
4 Correct 165 ms 504 KB Ok! 1573 queries used.
5 Correct 158 ms 504 KB Ok! 1459 queries used.
6 Correct 157 ms 504 KB Ok! 1531 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 504 KB Ok! 1587 queries used.
2 Correct 165 ms 616 KB Ok! 1558 queries used.