제출 #605799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605799		farhan132	ICC (CEOI16_icc)	C++17	0 / 100	7 ms	504 KiB

icc

#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);
    	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 == p[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]);
    }
} 

컴파일 시 표준 에러 (stderr) 메시지

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: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 < A.size(); i++) v2.pb(A[i]);
      |                     ~~^~~~~~~~~~
icc.cpp:98:84: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   98 |       if(p[(lower_bound(idx.begin(), idx.end(), T.find(A[0])) - idx.begin())] ^ xr == p[k]) _B.pb(i);
icc.cpp:106:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |       for(ll i = m; i < B.size(); i++) v2.pb(B[i]);
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10