oj.uz

Submission #605237

# Submission time Handle Problem Language Result Execution time Memory
605237 2022-07-25T14:28:07 Z HappyPacMan ICC (CEOI16_icc) C++14
100 / 100
 117 ms 508 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;
		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:31:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(currPow <= vst.size()/2){
      |         ~~~~~~~~^~~~~~~~~~~~~~~
icc.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int j=0;j<vst.size();j++){
      |                ~^~~~~~~~~~~
icc.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j=0;j<vst.size();j++){
      |               ~^~~~~~~~~~~
icc.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |    for(int j=0;j<left.size();j++){
      |                ~^~~~~~~~~~~~
icc.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    for(int j=0;j<right.size();j++){
      |                ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 500 KB Ok! 530 queries used.
2 Correct 35 ms 504 KB Ok! 648 queries used.
3 Correct 31 ms 508 KB Ok! 649 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 492 KB Ok! 1456 queries used.
2 Correct 111 ms 468 KB Ok! 1573 queries used.
3 Correct 98 ms 504 KB Ok! 1539 queries used.
4 Correct 106 ms 488 KB Ok! 1489 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 488 KB Ok! 1491 queries used.
2 Correct 98 ms 484 KB Ok! 1475 queries used.
3 Correct 108 ms 492 KB Ok! 1609 queries used.
4 Correct 97 ms 492 KB Ok! 1492 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 492 KB Ok! 1597 queries used.
2 Correct 99 ms 484 KB Ok! 1592 queries used.
3 Correct 102 ms 488 KB Ok! 1597 queries used.
4 Correct 115 ms 496 KB Ok! 1573 queries used.
5 Correct 96 ms 492 KB Ok! 1497 queries used.
6 Correct 103 ms 468 KB Ok! 1565 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 488 KB Ok! 1603 queries used.
2 Correct 107 ms 488 KB Ok! 1613 queries used.