oj.uz

Submission #605782

# Submission time Handle Problem Language Result Execution time Memory
605782 2022-07-26T02:16:40 Z farhan132 ICC (CEOI16_icc) C++17
90 / 100
 142 ms 616 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];
	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);


    	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)) break;
    	}
    	while(A.size() > 1){
    		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; 
    	}
    	while(B.size() > 1){
    		ll m = B.size()/2;
    		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:62:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |      for(ll i = 0; i < p.size(); i++) p[i] = i;
      |                    ~~^~~~~~~~~~
icc.cpp:81:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
      |                     ~~^~~~~~~~~~
icc.cpp:89:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |       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 5 ms 468 KB Ok! 105 queries used.
2 Correct 6 ms 468 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 512 KB Ok! 541 queries used.
2 Correct 39 ms 480 KB Ok! 674 queries used.
3 Correct 39 ms 488 KB Ok! 683 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 496 KB Ok! 1467 queries used.
2 Correct 129 ms 492 KB Ok! 1678 queries used.
3 Correct 125 ms 496 KB Ok! 1629 queries used.
4 Correct 131 ms 500 KB Ok! 1574 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 492 KB Ok! 1609 queries used.
2 Correct 120 ms 504 KB Ok! 1599 queries used.
3 Correct 134 ms 488 KB Ok! 1658 queries used.
4 Correct 119 ms 492 KB Ok! 1550 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 616 KB Ok! 1659 queries used.
2 Correct 127 ms 488 KB Ok! 1651 queries used.
3 Correct 133 ms 468 KB Ok! 1668 queries used.
4 Correct 129 ms 488 KB Ok! 1659 queries used.
5 Correct 116 ms 468 KB Ok! 1530 queries used.
6 Correct 120 ms 468 KB Ok! 1594 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 492 KB Too many queries! 1658 out of 1625
2 Halted 0 ms 0 KB -