oj.uz

Submission #312078

# Submission time Handle Problem Language Result Execution time Memory
312078 2020-10-12T09:56:22 Z talant117408 Mechanical Doll (IOI18_doll) C++17
100 / 100
 134 ms 13212 KB 
#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(int lvl = 0; lvl < K-1; lvl++){
            for(j = 0; j < (1 << lvl); j++){
                if((j << (K-lvl)) + (1 << (K-lvl)) <= (k-saizu)){
                    
                }
                else if((j << (K-lvl)) + (1 << (K-lvl-1)) <= (k-saizu)){
                    x.pb(id);
                    y.pb(--s);
                }
                else{
                    x.pb(--s);
                    y.pb(--s);
                }
            }
        }
        
        vector <int> go(k);
        int ptr = 0;
        for(j = 0; j < k; j++){
            if(rev[j] < (k-saizu)){
                
            }
            else{
                go[rev[j]] = after[ptr++];
            }
        }
        
        for(j = 0; j < k/2; j++){
            if(j*2+2 <= (k-saizu)){
                
            }
            else if(j*2+1 <= (k-saizu)){
                x.pb(id);
                y.pb(go[j*2+1]);
            }
            else{
                x.pb(go[j*2]);
                y.pb(go[j*2+1]);
            }
        }
        
        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;
    int id = generate(A, s, x, y);
    
    for(i = 0; i <= M; i++){
        connected[i] = id;
    }
    
    /*
    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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 8092 KB Output is correct
3 Correct 44 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 74 ms 10148 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 8092 KB Output is correct
3 Correct 44 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 74 ms 10148 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 9536 KB Output is correct
9 Correct 89 ms 11236 KB Output is correct
10 Correct 134 ms 13212 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 49 ms 8092 KB Output is correct
3 Correct 44 ms 6948 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 74 ms 10148 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 78 ms 9536 KB Output is correct
9 Correct 89 ms 11236 KB Output is correct
10 Correct 134 ms 13212 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 104 ms 10912 KB Output is correct
15 Correct 62 ms 7584 KB Output is correct
16 Correct 107 ms 9856 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 114 ms 11796 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 6704 KB Output is correct
3 Correct 49 ms 6220 KB Output is correct
4 Correct 74 ms 7600 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 57 ms 6704 KB Output is correct
3 Correct 49 ms 6220 KB Output is correct
4 Correct 74 ms 7600 KB Output is correct
5 Correct 96 ms 10148 KB Output is correct
6 Correct 92 ms 9508 KB Output is correct
7 Correct 102 ms 9652 KB Output is correct
8 Correct 88 ms 8984 KB Output is correct
9 Correct 47 ms 6316 KB Output is correct
10 Correct 94 ms 8764 KB Output is correct
11 Correct 83 ms 9216 KB Output is correct
12 Correct 51 ms 6724 KB Output is correct
13 Correct 62 ms 7404 KB Output is correct
14 Correct 61 ms 7624 KB Output is correct
15 Correct 67 ms 7872 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 49 ms 6560 KB Output is correct
18 Correct 51 ms 6628 KB Output is correct
19 Correct 52 ms 6728 KB Output is correct
20 Correct 82 ms 8228 KB Output is correct
21 Correct 74 ms 8960 KB Output is correct
22 Correct 108 ms 7968 KB Output is correct