oj.uz

Submission #162793

# Submission time Handle Problem Language Result Execution time Memory
162793 2019-11-09T19:20:59 Z Minnakhmetov Mechanical Doll (IOI18_doll) C++14
100 / 100
 397 ms 41632 KB 
#include "doll.h"
#include<bits/stdc++.h>
using namespace std;
 
#define all(aaa) aaa.begin(), aaa.end()
 
const int N = 1e6 + 5;
 
vector<int> tot, tosx, tosy, ct, w;
int z = 0, root = -1;
 
vector<int> ch[N];
int state[N];
 
int build(int L, int R, int &waste) {
    if (R - L + 1 <= waste) {        
        waste -= R - L + 1;
        return -1;
    }
    if (L == R)
        return 0;
    int v = ++z,
        m = (L + R) >> 1;
    ch[v] = {build(L, m, waste), build(m + 1, R, waste)};
    // cout << -v << " " << ch[v][0] << " " << ch[v][1] << "\n";
    return -v;
}
 
void create_circuit(int m, vector<int> a) {
    tot.resize(m + 1);
    ct.resize(m + 1);
 
    a.insert(a.begin(), 0);
    for (int x : a)
        ct[x]++;
    a.push_back(0);
 
    int n = a.size();
 
    // for (int x : a)
    //     cout << x << " ";
    // cout << "\n";
 
    for (int i = 0; i < n - 1; i++) {
        if (ct[a[i]] == 1) {
            tot[a[i]] = a[i + 1];
        }
        else {
            tot[a[i]] = -1;
            w.push_back(a[i + 1]);
        }
    }
 
    // for (int i = 0; i <= m; i++) {
    //     cout << tot[i] << " ";
    // }
    // cout << "\n";
 
 
 
    if (!w.empty()) {
        int k = 1, waste;
        while (k < w.size())
            k *= 2;
        waste = k - w.size();

        build(0, k - 1, waste);
 
        for (int x : w) {
            int y = root, py;
            while (y != 0) {
                py = y;
                y = ch[-py][state[-py]];
                state[-py] ^= 1;
            }
            ch[-py][state[-py] ^ 1] = x;
        }
    }
 
    tosx.resize(z);
    tosy.resize(z);
 
    for (int i = 1; i <= z; i++) {
        tosx[i - 1] = ch[i][0];
        tosy[i - 1] = ch[i][1];
    }
 
    // for (int x : tot)
    //     cout << x << " ";
    // cout << "\n";
    // for (int x : tosx)
    //     cout << x << " ";
    // cout << "\n";
    // for (int x : tosy) 
    //     cout << x << " ";
    // cout << "\n";
 
    answer(tot, tosx, tosy);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         while (k < w.size())
      |                ~~^~~~~~~~~~
doll.cpp:76:27: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |             ch[-py][state[-py] ^ 1] = x;
      |                           ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 40 ms 25740 KB Output is correct
3 Correct 36 ms 25448 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 30 ms 25292 KB Output is correct
6 Correct 46 ms 26252 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 40 ms 25740 KB Output is correct
3 Correct 36 ms 25448 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 30 ms 25292 KB Output is correct
6 Correct 46 ms 26252 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 196 ms 35412 KB Output is correct
9 Correct 182 ms 32756 KB Output is correct
10 Correct 385 ms 41632 KB Output is correct
11 Correct 16 ms 23756 KB Output is correct
12 Correct 16 ms 23768 KB Output is correct
13 Correct 17 ms 23784 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 40 ms 25740 KB Output is correct
3 Correct 36 ms 25448 KB Output is correct
4 Correct 16 ms 23780 KB Output is correct
5 Correct 30 ms 25292 KB Output is correct
6 Correct 46 ms 26252 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 196 ms 35412 KB Output is correct
9 Correct 182 ms 32756 KB Output is correct
10 Correct 385 ms 41632 KB Output is correct
11 Correct 16 ms 23756 KB Output is correct
12 Correct 16 ms 23768 KB Output is correct
13 Correct 17 ms 23784 KB Output is correct
14 Correct 355 ms 40956 KB Output is correct
15 Correct 186 ms 34716 KB Output is correct
16 Correct 294 ms 40600 KB Output is correct
17 Correct 16 ms 23756 KB Output is correct
18 Correct 16 ms 23784 KB Output is correct
19 Correct 16 ms 23732 KB Output is correct
20 Correct 374 ms 40480 KB Output is correct
21 Correct 15 ms 23756 KB Output is correct
22 Correct 17 ms 23724 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23756 KB Output is correct
2 Correct 18 ms 23684 KB Output is correct
3 Correct 16 ms 23756 KB Output is correct
4 Correct 16 ms 23756 KB Output is correct
5 Correct 19 ms 23756 KB Output is correct
6 Correct 16 ms 23684 KB Output is correct
7 Correct 24 ms 23736 KB Output is correct
8 Correct 16 ms 23756 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23708 KB Output is correct
2 Correct 189 ms 33644 KB Output is correct
3 Correct 233 ms 33712 KB Output is correct
4 Correct 345 ms 38932 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23708 KB Output is correct
2 Correct 189 ms 33644 KB Output is correct
3 Correct 233 ms 33712 KB Output is correct
4 Correct 345 ms 38932 KB Output is correct
5 Correct 282 ms 40408 KB Output is correct
6 Correct 374 ms 40100 KB Output is correct
7 Correct 334 ms 40228 KB Output is correct
8 Correct 371 ms 39716 KB Output is correct
9 Correct 197 ms 33596 KB Output is correct
10 Correct 368 ms 39624 KB Output is correct
11 Correct 397 ms 39292 KB Output is correct
12 Correct 210 ms 33920 KB Output is correct
13 Correct 172 ms 34404 KB Output is correct
14 Correct 163 ms 34448 KB Output is correct
15 Correct 170 ms 34644 KB Output is correct
16 Correct 19 ms 24008 KB Output is correct
17 Correct 152 ms 33916 KB Output is correct
18 Correct 221 ms 33912 KB Output is correct
19 Correct 255 ms 33852 KB Output is correct
20 Correct 373 ms 39464 KB Output is correct
21 Correct 291 ms 39312 KB Output is correct
22 Correct 296 ms 39288 KB Output is correct