oj.uz

Submission #605820

# Submission time Handle Problem Language Result Execution time Memory
605820 2022-07-26T02:45:48 Z maximath_1 ICC (CEOI16_icc) C++11
100 / 100
 781 ms 668 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
 
const int MX = 105;

int que(vector<int> lf, vector<int> rg){
	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()) return 0;
	return query(lf.size(), rg.size(), xl, xr);
}
 
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;
				}
            }
            gt = que(lf, rg);
          	if(gt == 0){
              for(int i : lf) for(int j : rg) ban[i][j] = ban[j][i] = 1;
			}
		}while(gt == 0);
 
		while(lf.size() > 1 || rg.size() > 1){
			shuffle(lf.begin(), lf.end(), rng);
			shuffle(rg.begin(), rg.end(), rng);

			vector<int> a, b;
			if(lf.size() > 1){
				for(int i = 0; i < lf.size(); i ++)
					(i % 2 ? a : b).push_back(lf[i]);
				if(que(a, rg)) lf = a;
				else lf = b;
			}

			vector<int> RR;
			for(int i : rg){
				bool ok = 0;
				for(int j : lf) if(!ban[i][j]){
					ok = 1; break;
				}
				if(ok) RR.push_back(i);
			}
			rg = RR;

			if(rg.size() > 1){
				a.clear(); b.clear();
				for(int i = 0; i < rg.size(); i ++)
					(i % 2 ? a : b).push_back(rg[i]);
				if(que(lf, a)) rg = a;
				else rg = b;
			}

			vector<int> LL;
			for(int i : lf){
				bool ok = 0;
				for(int j : rg) if(!ban[i][j]){
					ok = 1; break;
				}
				if(ok) LL.push_back(i);
			}
			lf = LL;
		}

		int u = lf[0], v = rg[0];
		setRoad(u, v);
		u = find(u); v = find(v);
		par[u] = v;
	}
}

Compilation message

icc.cpp: In function 'int que(std::vector<int>, std::vector<int>)':
icc.cpp:9:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                 ~~^~~~~~~~~~~
icc.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
      |                 ~~^~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < lf.size(); i ++)
      |                    ~~^~~~~~~~~~~
icc.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i = 0; i < rg.size(); i ++)
      |                    ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 468 KB Ok! 97 queries used.
2 Correct 7 ms 544 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 528 KB Ok! 515 queries used.
2 Correct 174 ms 524 KB Ok! 460 queries used.
3 Correct 107 ms 468 KB Ok! 477 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 540 KB Ok! 1258 queries used.
2 Correct 751 ms 540 KB Ok! 1088 queries used.
3 Correct 298 ms 532 KB Ok! 1247 queries used.
4 Correct 460 ms 544 KB Ok! 1233 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 536 KB Ok! 1229 queries used.
2 Correct 431 ms 532 KB Ok! 1227 queries used.
3 Correct 599 ms 532 KB Ok! 1183 queries used.
4 Correct 300 ms 536 KB Ok! 1260 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 544 KB Ok! 1193 queries used.
2 Correct 626 ms 532 KB Ok! 1181 queries used.
3 Correct 781 ms 532 KB Ok! 1179 queries used.
4 Correct 564 ms 540 KB Ok! 1220 queries used.
5 Correct 363 ms 536 KB Ok! 1263 queries used.
6 Correct 503 ms 668 KB Ok! 1242 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 528 KB Ok! 1186 queries used.
2 Correct 722 ms 656 KB Ok! 1123 queries used.