oj.uz

Submission #605823

# Submission time Handle Problem Language Result Execution time Memory
605823 2022-07-26T02:48:32 Z HappyPacMan ICC (CEOI16_icc) C++14
100 / 100
 117 ms 504 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int reqA[104],reqB[104],DSU[104];
 
int par(int u){
	return DSU[u] = DSU[u] == u ? u : par(DSU[u]);
}
void join(int x,int y){
	x = par(x);
	y = par(y);
	DSU[x] = y;
}
 
void run(int N){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	iota(DSU,DSU+104,0);
	for(int i=1;i<N;i++){
		set<int> st;
		vector<int> vec[104];
		for(int j=1;j<=N;j++){
			par(j);
			st.emplace(DSU[j]);
			vec[DSU[j]].emplace_back(j);
		}
		vector<int> vst;
		for(int it : st){
			vst.emplace_back(it);
		}
		int currPow = 1;
      	shuffle(vst.begin(),vst.end(),rng);
		while(currPow <= vst.size()/2){
			int size_a = 0, size_b = 0;
			for(int j=0;j<vst.size();j++){
				if(j & currPow){
					for(int it : vec[vst[j]]){
						reqA[size_a++] = it;
					}
				}else{
					for(int it : vec[vst[j]]){
						reqB[size_b++] = it;
					}
				}
			}
			if(query(size_a,size_b,reqA,reqB)){
				break;
			}else{
				currPow <<= 1;
			}
		}
		vector<int> left,right;
		for(int j=0;j<vst.size();j++){
			if(j & currPow){
				for(int it : vec[vst[j]]){
					left.emplace_back(it);
				}
			}else{
				for(int it : vec[vst[j]]){
					right.emplace_back(it);
				}
			}
		}
		int size_a, size_b;
 
		size_b = 0;
		for(int it : right){
			reqB[size_b++] = it;
		}
		while(left.size() > 1){
			int sz = left.size()/2;
			vector<int> vlef,vrig;
			for(int j=0;j<left.size();j++){
				if(j < sz){
					vlef.emplace_back(left[j]);
				}else{
					vrig.emplace_back(left[j]);
				}
			}
			size_a = 0;
			for(int it : vlef){
				reqA[size_a++] = it;
			}
			if(query(size_a,size_b,reqA,reqB)){
				left = vlef;
			}else{
				left = vrig;
			}
		}
 
		size_b = 0;
		for(int it : left){
			reqB[size_b++] = it;
		}
		while(right.size() > 1){
			int sz = right.size()/2;
			vector<int> vlef,vrig;
			for(int j=0;j<right.size();j++){
				if(j < sz){
					vlef.emplace_back(right[j]);
				}else{
					vrig.emplace_back(right[j]);
				}
			}
			size_a = 0;
			for(int it : vlef){
				reqA[size_a++] = it;
			}
			if(query(size_a,size_b,reqA,reqB)){
				right = vlef;
			}else{
				right = vrig;
			}
		}
		setRoad(left.back(),right.back());
		join(left.back(),right.back());
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(currPow <= vst.size()/2){
      |         ~~~~~~~~^~~~~~~~~~~~~~~
icc.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int j=0;j<vst.size();j++){
      |                ~^~~~~~~~~~~
icc.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j=0;j<vst.size();j++){
      |               ~^~~~~~~~~~~
icc.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int j=0;j<left.size();j++){
      |                ~^~~~~~~~~~~~
icc.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for(int j=0;j<right.size();j++){
      |                ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 108 queries used.
2 Correct 4 ms 468 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Ok! 537 queries used.
2 Correct 32 ms 468 KB Ok! 651 queries used.
3 Correct 35 ms 492 KB Ok! 664 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 468 KB Ok! 1434 queries used.
2 Correct 115 ms 496 KB Ok! 1584 queries used.
3 Correct 102 ms 468 KB Ok! 1560 queries used.
4 Correct 101 ms 496 KB Ok! 1517 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 492 KB Ok! 1478 queries used.
2 Correct 102 ms 496 KB Ok! 1509 queries used.
3 Correct 108 ms 500 KB Ok! 1594 queries used.
4 Correct 97 ms 504 KB Ok! 1474 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 496 KB Ok! 1589 queries used.
2 Correct 110 ms 500 KB Ok! 1589 queries used.
3 Correct 109 ms 468 KB Ok! 1586 queries used.
4 Correct 111 ms 496 KB Ok! 1588 queries used.
5 Correct 100 ms 468 KB Ok! 1501 queries used.
6 Correct 109 ms 496 KB Ok! 1566 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 468 KB Ok! 1608 queries used.
2 Correct 117 ms 492 KB Ok! 1598 queries used.