제출 #312068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312068		talant117408	자동 인형 (IOI18_doll)	C++17	53 / 100	133 ms	13968 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int generate(vector <int> &after, int &s, vector <int> &x, vector <int> &y){
    int saizu = sz(after);
    if(!saizu){
        return 0;
    }
    else if(saizu == 1){
        return after[0];
    }
    else{
        int j, k = 1, K = 0;
        while(k < saizu) {
            k *= 2;
            K++;
        }
        
        vector <int> rev(k);
        for(j = 0; j < k; j++){
            rev[j] = rev[j/2]/2 | ((j&1) << (K-1));
        }
        
        int id = --s;
        for(j = 0; j < (k-1)/2; j++){
            x.pb(--s);
            y.pb(--s);
        }
        
        for(j = 0; j < k; j++){
            vector <int>& where = j&1 ? y : x;
            if(rev[j] < (k-saizu)) where.pb(id);
            else where.pb(after[rev[j]-(k-saizu)]);
        }
        return id;
    }
}

void create_circuit(int M, vector<int> A){
    int i;
    vector <vector <int>> after(M+1);
    vector <int> connected(M+1), x, y;
    A.pb(0);
    
    int n = sz(A);
    
    for(i = 0; i < n; i++){
        after[A[i]].pb(A[(i+1)%n]);
    }
    
    int s = 0;
    
    for(i = 0; i <= M; i++){
        connected[i] = generate(after[i], s, x, y);
    }
    
    /*
    for(auto to : connected) cout << to << ' ';
    cout << endl;
    for(i = 0; i < sz(x); i++) cout << x[i] << ' ' << y[i] << endl;
    */
    answer(connected, x, y);
}

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