oj.uz

Submission #655161

# Submission time Handle Problem Language Result Execution time Memory
655161 2022-11-03T12:52:15 Z Ronin13 Mechanical Doll (IOI18_doll) C++14
100 / 100
 510 ms 180760 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back

using namespace std;

const int NMAX = 1e6 + 1;
vector <vector <int> > g(NMAX);

int cur = 1;

void build(int v, int l, int r, int st, int fin){
    if(l == r){
        if(r == fin){
            g[v].pb(v);
            g[v].pb(0);
            return;
        }
        g[v].pb(1);
        return;
    }
    int m = (l + r) / 2;
    if(m < st || m > fin){
        g[v].pb(1);
        cur++;
        g[v].pb(cur);
        build(cur, m + 1, r, st, fin);
    }
    else{
        cur++;
        g[v].pb(cur);
        build(cur, l, m, st, fin);
        cur++;
        g[v].pb(cur);
        build(cur, m + 1, r, st, fin);
    }
}

vector <int> trav;
vector <int> state(NMAX, 1);

void traverse(int v, int x){
    if(trav.size() == x) return;
    if(g[v].size() == 1){
        trav.pb(v);
        traverse(g[v][0], x);
    }
    else{
        state[v] ^= 1;
        traverse(g[v][state[v]], x);
    }
}

vector <int> ind(NMAX);
vector <int> c, X, Y;
void create_circuit(int M, std::vector<int> A) {
    c.resize(M + 1);
    int n = A.size();
    int x = log2(n);
    if(__builtin_popcount(n) > 1) x++;
    build(1, 1, (1 << x), (1 << x) - n + 1, (1 << x));
    traverse(1, n - 1);

    c[A[0]] = -1;
    c[0] = A[0];
    for(int i = 0; i < trav.size(); i++){
        //cout << trav[i];
        ind[trav[i]] = A[i + 1];
    }
    int cc = -1;
    for(int i = 1; i <= cur; i++){
        if(g[i].size() >= 2){
            ind[i] = cc--;
        }
    }


    X.resize((int)abs(cc + 1));
    Y.resize((int)abs(cc + 1));
    for(int i = 1; i <= cur; i++){
        if(g[i].size() == 1){
            c[ind[i]] = ind[g[i][0]];
        }
        else{
            X[-ind[i] - 1] = ind[g[i][0]];
            Y[-ind[i] - 1] = ind[g[i][1]];
        }
    }

    /*for(int to : c){
        cout << to << ' ';
    }
    cout << "\n";
    for(int i = 0; i < X.size(); i++){
        cout << X[i] << ' ' << Y[i] << "\n";
    }*/
    answer(c, X, Y);
}

Compilation message

doll.cpp: In function 'void traverse(int, int)':
doll.cpp:50:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if(trav.size() == x) return;
      |        ~~~~~~~~~~~~^~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < trav.size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 123 ms 74660 KB Output is correct
3 Correct 128 ms 82468 KB Output is correct
4 Correct 17 ms 31624 KB Output is correct
5 Correct 26 ms 32704 KB Output is correct
6 Correct 220 ms 103412 KB Output is correct
7 Correct 17 ms 31572 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 123 ms 74660 KB Output is correct
3 Correct 128 ms 82468 KB Output is correct
4 Correct 17 ms 31624 KB Output is correct
5 Correct 26 ms 32704 KB Output is correct
6 Correct 220 ms 103412 KB Output is correct
7 Correct 17 ms 31572 KB Output is correct
8 Correct 309 ms 120304 KB Output is correct
9 Correct 309 ms 136940 KB Output is correct
10 Correct 496 ms 180760 KB Output is correct
11 Correct 18 ms 31564 KB Output is correct
12 Correct 17 ms 31508 KB Output is correct
13 Correct 20 ms 31576 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 123 ms 74660 KB Output is correct
3 Correct 128 ms 82468 KB Output is correct
4 Correct 17 ms 31624 KB Output is correct
5 Correct 26 ms 32704 KB Output is correct
6 Correct 220 ms 103412 KB Output is correct
7 Correct 17 ms 31572 KB Output is correct
8 Correct 309 ms 120304 KB Output is correct
9 Correct 309 ms 136940 KB Output is correct
10 Correct 496 ms 180760 KB Output is correct
11 Correct 18 ms 31564 KB Output is correct
12 Correct 17 ms 31508 KB Output is correct
13 Correct 20 ms 31576 KB Output is correct
14 Correct 494 ms 180260 KB Output is correct
15 Correct 309 ms 137200 KB Output is correct
16 Correct 499 ms 180048 KB Output is correct
17 Correct 16 ms 31572 KB Output is correct
18 Correct 17 ms 31628 KB Output is correct
19 Correct 17 ms 31572 KB Output is correct
20 Correct 493 ms 180572 KB Output is correct
21 Correct 16 ms 31572 KB Output is correct
22 Correct 16 ms 31500 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31608 KB Output is correct
2 Correct 17 ms 31608 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct
5 Correct 15 ms 31612 KB Output is correct
6 Correct 18 ms 31628 KB Output is correct
7 Correct 17 ms 31516 KB Output is correct
8 Correct 16 ms 31624 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31556 KB Output is correct
2 Correct 291 ms 119272 KB Output is correct
3 Correct 325 ms 135864 KB Output is correct
4 Correct 482 ms 179060 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31556 KB Output is correct
2 Correct 291 ms 119272 KB Output is correct
3 Correct 325 ms 135864 KB Output is correct
4 Correct 482 ms 179060 KB Output is correct
5 Correct 500 ms 179928 KB Output is correct
6 Correct 501 ms 179496 KB Output is correct
7 Correct 483 ms 179844 KB Output is correct
8 Correct 485 ms 179316 KB Output is correct
9 Correct 322 ms 136252 KB Output is correct
10 Correct 485 ms 179376 KB Output is correct
11 Correct 484 ms 179068 KB Output is correct
12 Correct 303 ms 135748 KB Output is correct
13 Correct 298 ms 119576 KB Output is correct
14 Correct 308 ms 136152 KB Output is correct
15 Correct 326 ms 136160 KB Output is correct
16 Correct 20 ms 34260 KB Output is correct
17 Correct 284 ms 119316 KB Output is correct
18 Correct 300 ms 119308 KB Output is correct
19 Correct 295 ms 135784 KB Output is correct
20 Correct 510 ms 179264 KB Output is correct
21 Correct 487 ms 179064 KB Output is correct
22 Correct 482 ms 179228 KB Output is correct