oj.uz

Submission #605814

# Submission time Handle Problem Language Result Execution time Memory
605814 2022-07-26T02:38:48 Z farhan132 ICC (CEOI16_icc) C++17
100 / 100
 122 ms 508 KB 
#include "icc.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

ll Q(vector < ll > a, vector < ll > b){
	if(min(a.size(), b.size()) == 0) return 0;
	ll sz1 = a.size(); ll A[sz1];
	ll sz2 = b.size(); ll B[sz2];
	for(ll i = 0; i < sz1; i++) A[i] = a[i];
	for(ll i = 0; i < sz2; i++) B[i] = b[i];
	// for(auto u : a) cout << u << ' ';
	// cout << '\n';
	// for(auto u : b) cout << u << ' ';
	// cout << '\n';
	return query(sz1,sz2,A,B);
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct DSU{
    vector < int > par;
    void start(int n){
        par.resize(n + 1);
        for(int i = 0; i <= n; i++) par[i] = i;
    }
    int find(int a){
        if(a == par[a]) return a;
        return par[a] = find(par[a]);
    }
    void merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return;
        if(rng()&1) swap(x,y);
        par[x] = y;
        return;
    }
}T;




void run(int n) {
    T.start(n);
    for(ll itr = 1; itr < n; itr++){
    	vector < ll > bit = {0,1,2,3,4,5,6};
    	//shuffle(bit.begin(), bit.end(), rng);
    	vector < ll > A,B;

    	vector < ll > idx;

    	for(ll i = 1; i <= n; i++){
    		idx.pb(T.find(i));
    	}
    	sort(idx.begin(), idx.end());
    	idx.erase(unique(idx.begin(), idx.end()), idx.end());
    	vector < ll > p(idx.size());
    	for(ll i = 0; i < p.size(); i++) p[i] = i;
    	shuffle(p.begin(), p.end(), rng);
    	ll xr = 0;
    	vector < ll > _A, _B;
    	for(auto j : bit){
    		A.clear();
    		B.clear();
    		for(ll i = 1; i <= n; i++){
    			ll k = lower_bound(idx.begin(), idx.end(), T.find(i)) - idx.begin();
    			k = p[k];
    			if((k >> j)&1) A.pb(i);
    			else B.pb(i);
    		}
    		if(Q(A,B)){
    			_A = A;
    		    _B = B;
    		    xr |= (1 << j);
    		}
    	}
    	A = _A;
    	B = _B;
    	if(B.size() > A.size()) swap(A,B);
    	while(A.size() > 1){
    		shuffle(A.begin(), A.end(), rng);
    		ll m = A.size()/2;
    		vector < ll > v1, v2;
    		for(ll i = 0; i < m; i++) v1.pb(A[i]);
    		for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
    		if(Q(v1, B)) A = v1;
    		else A = v2; 
    	}
    	_B.clear();

    	for(ll i = 1; i <= n; i++){
    		ll k = lower_bound(idx.begin(), idx.end(), T.find(i)) - idx.begin();
    		k = p[k];
    		if((p[(lower_bound(idx.begin(), idx.end(), T.find(A[0])) - idx.begin())] ^ xr) == k) _B.pb(i);
    	}
    	B = _B;
    	while(B.size() > 1){
    		ll m = B.size()/2;
    		shuffle(B.begin(), B.end(), rng);
    		vector < ll > v1, v2;
    		for(ll i = 0; i < m; i++) v1.pb(B[i]);
    		for(ll i = m; i < B.size(); i++) v2.pb(B[i]);
    		if(Q(A, v1)) B = v1;
    		else B = v2; 
    	}
    	setRoad(A[0], B[0]);
    	T.merge(A[0], B[0]);
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:66:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |      for(ll i = 0; i < p.size(); i++) p[i] = i;
      |                    ~~^~~~~~~~~~
icc.cpp:93:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |       for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
      |                     ~~^~~~~~~~~~
icc.cpp:110:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |       for(ll i = m; i < B.size(); i++) v2.pb(B[i]);
      |                     ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 496 KB Ok! 518 queries used.
2 Correct 28 ms 468 KB Ok! 541 queries used.
3 Correct 27 ms 504 KB Ok! 539 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 504 KB Ok! 1279 queries used.
2 Correct 101 ms 496 KB Ok! 1320 queries used.
3 Correct 92 ms 496 KB Ok! 1301 queries used.
4 Correct 94 ms 500 KB Ok! 1300 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 500 KB Ok! 1270 queries used.
2 Correct 101 ms 504 KB Ok! 1285 queries used.
3 Correct 95 ms 496 KB Ok! 1309 queries used.
4 Correct 94 ms 496 KB Ok! 1282 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 504 KB Ok! 1277 queries used.
2 Correct 101 ms 488 KB Ok! 1329 queries used.
3 Correct 116 ms 492 KB Ok! 1318 queries used.
4 Correct 113 ms 468 KB Ok! 1293 queries used.
5 Correct 94 ms 484 KB Ok! 1293 queries used.
6 Correct 103 ms 488 KB Ok! 1307 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 508 KB Ok! 1303 queries used.
2 Correct 114 ms 496 KB Ok! 1337 queries used.