oj.uz

Submission #605810

# Submission time Handle Problem Language Result Execution time Memory
605810 2022-07-26T02:35:16 Z maximath_1 ICC (CEOI16_icc) C++11
90 / 100
 836 ms 544 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_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int ban[MX][MX];
void run(int N){
	for(int i = 1; i <= N; i ++)
		par[i] = i;
	for(int times = 1; times < N; times ++){
      	memset(ban, 0, sizeof(ban));
		vector<int> color(N + 1, -1), lf, rg;
		set<vector<int> > cc;
		int gt = 0;
		do{
          	int mx = 0;
          	for(int _ = 0; _ < 200; _ ++){
            	for(int i = 1; i <= N; i ++) if(find(i) == i)
					color[i] = rng() % 2;
            	for(int i = 1; i <= N; i ++) color[i] = color[find(i)];
            	vector<int> nlf, nrg;
            	for(int i = 1; i <= N; i ++)
            		if(color[i]) nrg.push_back(i);
            		else nlf.push_back(i);
            	int cnt = 0;
            	for(int i : nlf) for(int j : nrg) cnt += !ban[i][j];
            	if(mx < cnt){
            		mx = cnt; lf = nlf; rg = nrg;
				}
            }
			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 == 0){
              for(int i : lf) for(int j : rg) ban[i][j] = ban[j][i] = 1;
			}
		}while(gt == 0);
 
		int l = 0, r = rg.size() - 1, rs = r + 1;
		for(int md; l <= r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = 0; 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){
				rs = md; r = md - 1;
			}else{
				l = md + 1;
			}
		}
 
		int u = rg[rs]; rg.clear(); rg.push_back(u);
		swap(lf, rg);
 
		l = 0, r = rg.size() - 1, rs = r + 1;
		for(int md; l <= r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = 0; 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){
				rs = md; r = md - 1;
			}else{
				l = md + 1;
			}
		}
 
		int v = rg[rs];
 
		setRoad(u, v);
		u = find(u); v = find(v);
		par[u] = v;
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
      |                   ~~^~~~~~~~~~~~
icc.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    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 7 ms 468 KB Ok! 104 queries used.
2 Correct 8 ms 540 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 532 KB Ok! 530 queries used.
2 Correct 137 ms 520 KB Ok! 716 queries used.
3 Correct 129 ms 468 KB Ok! 709 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 528 KB Ok! 1348 queries used.
2 Correct 836 ms 528 KB Ok! 1817 queries used.
3 Correct 317 ms 532 KB Ok! 1385 queries used.
4 Correct 498 ms 528 KB Ok! 1513 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 536 KB Ok! 1437 queries used.
2 Correct 361 ms 536 KB Ok! 1451 queries used.
3 Correct 601 ms 524 KB Ok! 1675 queries used.
4 Correct 220 ms 536 KB Ok! 1317 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 524 KB Ok! 1687 queries used.
2 Correct 643 ms 532 KB Ok! 1701 queries used.
3 Correct 618 ms 528 KB Ok! 1720 queries used.
4 Correct 537 ms 544 KB Ok! 1623 queries used.
5 Correct 345 ms 532 KB Ok! 1447 queries used.
6 Correct 523 ms 528 KB Ok! 1621 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 607 ms 532 KB Too many queries! 1707 out of 1625
2 Halted 0 ms 0 KB -