oj.uz

Submission #605791

# Submission time Handle Problem Language Result Execution time Memory
605791 2022-07-26T02:22:24 Z farhan132 ICC (CEOI16_icc) C++17
90 / 100
 144 ms 588 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){
    		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; 
    	}
    	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: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:82:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |       for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
      |                     ~~^~~~~~~~~~
icc.cpp:91:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       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! 96 queries used.
2 Correct 5 ms 468 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 468 KB Ok! 538 queries used.
2 Correct 37 ms 480 KB Ok! 688 queries used.
3 Correct 34 ms 468 KB Ok! 675 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 492 KB Ok! 1412 queries used.
2 Correct 128 ms 484 KB Ok! 1671 queries used.
3 Correct 103 ms 496 KB Ok! 1534 queries used.
4 Correct 106 ms 500 KB Ok! 1520 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 504 KB Ok! 1541 queries used.
2 Correct 109 ms 492 KB Ok! 1514 queries used.
3 Correct 130 ms 488 KB Ok! 1633 queries used.
4 Correct 102 ms 488 KB Ok! 1460 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 504 KB Ok! 1619 queries used.
2 Correct 144 ms 488 KB Ok! 1640 queries used.
3 Correct 115 ms 504 KB Ok! 1649 queries used.
4 Correct 109 ms 488 KB Ok! 1617 queries used.
5 Correct 121 ms 588 KB Ok! 1499 queries used.
6 Correct 111 ms 504 KB Ok! 1575 queries used.

Subtask #6
0 / 10.0

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