제출 #442832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442832		vanic	자동 인형 (IOI18_doll)	C++14	6 / 100	1088 ms	12088 KiB

doll

    #include "doll.h"
    #include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <stack>
     
    using namespace std;
     
    const int maxn=1e5+5, Log=17, pot=(1<<Log), inf=1e9;
     
    vector < int > sus[maxn];
    vector < int > vez;
    vector < int > x, y;
    int m, n;
    vector < int > red;
    bool crna[pot];
     
    void napravi(int bit){
    	int br=0;
    	for(int i=0; i<(1<<bit); i++){
    		red.push_back(br);
    		for(int j=bit-1; j>-1; j--){
    			if((1<<j)&br){
    				br-=(1<<j);
    			}
    			else{
    				br+=(1<<j);
    				break;
    			}
    		}
    	}
    /*	for(int i=0; i<red.size(); i++){
    		cout << red[i] << ' ';
    	}
    	cout << endl;*/
    }
     
    int bit;
    int poz;
    int mini;
    int tren;
     
    struct Logaritamska{
    	vector < int > l;
    	int siz;
    	void precompute(int sz){
    		siz=sz;
    		l.clear();
    		while(sz--){
    			l.push_back(0);
    		}
    	}
    	void update(int x, int val){
    		for(; x<siz; x+=(x & -x)){
    			l[x]+=val;
    		}
    	}
    	int query(int x){
    		int sol=0;
    		for(; x>0; x-=(x & -x)){
    			sol+=l[x];
    		}
    		return sol;
    	}
    };
     
     
    Logaritamska L;
     
     
     
    int siri(int cor, int val, int dep, int pos){
    	if(bit==dep){
    //		cout << red[cor] << endl;
    		if(L.query(red[cor])==L.query(red[cor]-1)){
    			int ind=red[cor]-L.query(red[cor]);
    			return sus[tren][ind];
    		}
    		else{
    			return inf;
    		}
    	}
    	int a, b;
    	x.push_back(0);
    	y.push_back(0);
    	mini=min(mini, val);
    	a=siri(cor, val-1, dep+1, pos);
    	b=siri(cor+(1<<(bit-dep-1)), mini-1, dep+1, pos);
    	if(a==inf && b==inf){
    		x.pop_back();
    		y.pop_back();
    		if(mini==val){
    			mini++;
    		}
    		return inf;
    	}
    	if(b==inf){
    		b=pos;
    	}
    	else if(a==inf){
    		a=pos;
    	}
    	x[-1-val]=a;
    	y[-1-val]=b;
    	return val;
    }
     
    void rijesi(){
    	int br;
    	int pos=-1;
    	int raz;
    	for(int i=1; i<=m; i++){
    //		cout << "usao" << endl;
    		tren=i;
    		if(sus[i].empty()){
    			vez.push_back(0);
    		}
    		else if(sus[i].size()==1){
    			vez.push_back(sus[i][0]);
    		}
    		else{
    			br=1;
    			bit=0;
    			while((int)sus[i].size()>br){
    				br*=2;
    				bit++;
    			}
    			red.clear();
    			napravi(bit);
    			L.precompute(br);
    			raz=br-sus[i].size();
    			for(int j=0; j<raz; j++){
    //				cout << "ne " << red[j] << endl;
    				L.update(red[j], 1);
    			}
    			vez.push_back(siri(0, pos, 0, pos));
    			pos=mini-1;
    		}
    	}
    }
     
    void create_circuit(int M, vector <int> a){
    	m=M;
    	n=a.size();
    	a.push_back(0);
    	vez.push_back(a[0]);
    	for(int i=0; i<n; i++){
    		sus[a[i]].push_back(a[i+1]);
    	}
    	rijesi();
    /*	for(int i=0; i<(int)vez.size(); i++){
    		cout << vez[i] << ' ';
    	}
    	cout << endl;
    	for(int i=0; i<(int)x.size(); i++){
    		cout << x[i] << ' ' << y[i] << endl;
    	}*/
    	answer(vez, x, y);
    }

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56