oj.uz

Submission #604936

# Submission time Handle Problem Language Result Execution time Memory
604936 2022-07-25T10:55:53 Z maximath_1 ICC (CEOI16_icc) C++11
100 / 100
 107 ms 500 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
 
const int MX = 105;
 
int par[MX];
int find(int nw){
	return par[nw] = (par[nw] == nw ? nw : find(par[nw]));
}
mt19937 rng(0);
void run(int N){
	for(int i = 1; i <= N; i ++)
		par[i] = i;
	for(int times = 1; times < N; times ++){
		vector<int> color(N + 1, -1), lf, rg;
		int gt = 0;
		
		for(int xx = 0; xx <= 7; xx ++){
			int i = xx;
			int tp = 1;
			for(int j = 1; j <= N; j ++) if(find(j) == j){
				if(tp & (1 << i)) color[j] = 1;
				else color[j] = 0;
				tp ++;
			}
			for(int j = 1; j <= N; j ++) color[j] = color[find(j)];
			lf.clear(); rg.clear();
			for(int j = 1; j <= N; j ++)
				if(color[j] == 1) lf.push_back(j);
				else rg.push_back(j);
			int xl[lf.size()], xr[rg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
			if(lf.empty() || rg.empty()) continue;
			gt = query(lf.size(), rg.size(), xl, xr);
			if(gt == 1) break;
		}
 	
		int l = 0, r = (int)rg.size() - 1;
		for(int md; l < r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = l; j <= md; j ++) nrg.push_back(rg[j]);
			int xl[lf.size()], xr[nrg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
			gt = query(lf.size(), nrg.size(), xl, xr);
		
			if(gt){
				r = md;
			}else{
				l = md + 1;
			}
		}
 
		int u = rg[r]; rg.clear(); rg.push_back(u);
		swap(lf, rg);
 
		l = 0, r = (int)rg.size() - 1;
		for(int md; l < r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = l; j <= md; j ++) nrg.push_back(rg[j]);
			int xl[lf.size()], xr[nrg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
			gt = query(lf.size(), nrg.size(), xl, xr);
			if(gt){
				r = md;
			}else{
				l = md + 1;
			}
		}
 
		int v = rg[r];
 
		setRoad(u, v);
		u = find(u); v = find(v);
		par[v] = u;
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
      |                   ~~^~~~~~~~~~~~
icc.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
      |                   ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 496 KB Ok! 538 queries used.
2 Correct 32 ms 496 KB Ok! 635 queries used.
3 Correct 35 ms 468 KB Ok! 640 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 480 KB Ok! 1415 queries used.
2 Correct 105 ms 468 KB Ok! 1594 queries used.
3 Correct 98 ms 496 KB Ok! 1575 queries used.
4 Correct 94 ms 468 KB Ok! 1487 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 496 KB Ok! 1504 queries used.
2 Correct 98 ms 468 KB Ok! 1499 queries used.
3 Correct 100 ms 484 KB Ok! 1591 queries used.
4 Correct 95 ms 488 KB Ok! 1421 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 484 KB Ok! 1567 queries used.
2 Correct 105 ms 468 KB Ok! 1573 queries used.
3 Correct 104 ms 488 KB Ok! 1610 queries used.
4 Correct 100 ms 468 KB Ok! 1563 queries used.
5 Correct 94 ms 484 KB Ok! 1463 queries used.
6 Correct 95 ms 468 KB Ok! 1501 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 484 KB Ok! 1616 queries used.
2 Correct 107 ms 484 KB Ok! 1591 queries used.