oj.uz

Submission #310959

# Submission time Handle Problem Language Result Execution time Memory
310959 2020-10-08T19:18:21 Z aZvezda Mechanical Doll (IOI18_doll) C++14
100 / 100
 153 ms 11976 KB 
#include "doll.h"

#include <vector>

void create_circuit(int M, std::vector<int> A);

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "

const int WRONG_ID = -16969420, ROOT_ID = WRONG_ID + 1;
vector<int> arr;
vector<int> x, y;

pair<int, int> buildTree(int l, int r) {
    if(l == r) {
        return {arr[l], arr[l] != WRONG_ID};
    }
    int m = (l + r) / 2ll;
    auto lftSon = buildTree(l, m);
    auto rghtSon = buildTree(m + 1, r);

    if(lftSon.second + rghtSon.second == 0) {
        return {WRONG_ID, 0};
    } else {
        x.push_back(lftSon.first);
        y.push_back(rghtSon.first);
        return {-x.size(), lftSon.second + rghtSon.second};
    }
}

int bitInverse(int ind, int pow2) {
    int ret = 0;
    for(int i = 0; i < pow2; i ++) {
        if(ind & (1 << i)) {
            ret |= (1 << (pow2 - 1 - i));
        }
    }
    return ret;
}

void create_circuit(int M, std::vector<int> A) {
    arr = A;
    arr.push_back(0);
    int pow2 = 0, big = 1, small;
    while((1 << pow2) < arr.size()) {pow2 ++;}
    while(big <= arr.size()) {big *= 2;} big /= 2;
    small = arr.size() - big;

    while(arr.size() < (1 << pow2)) {
        arr.push_back(WRONG_ID);
    }
    vector<pair<int, int> > pairs;
    for(int i = 0; i < big; i ++) {
        int inv = bitInverse(i, pow2);
        pairs.push_back({inv, -1});
    }
    for(int i = arr.size() - small; i < arr.size(); i ++) {
        int inv = bitInverse(i, pow2);
        pairs.push_back({inv, -1});
    }
    sort(pairs.begin(), pairs.end());
    for(int i = 0; i < pairs.size(); i ++) {
        pairs[i].second = arr[i];
    }
    for(auto &it : arr) {it = WRONG_ID;}
    for(int i = 0; i < pairs.size(); i ++) {
        arr[bitInverse(pairs[i].first, pow2)] = pairs[i].second;
    }
    pow2 = 1 << pow2;
    int root = buildTree(0, pow2 - 1).first;
    vector<int> ptr;
    for(int i = 0; i <= M; i ++) {
        ptr.push_back(root);
    }
    for(int i = 0; i < x.size(); i ++) {
        if(x[i] == WRONG_ID) {
            x[i] = root;
        }
        if(y[i] == WRONG_ID) {
            y[i] = root;
        }
    }
    answer(ptr, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     while((1 << pow2) < arr.size()) {pow2 ++;}
      |           ~~~~~~~~~~~~^~~~~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while(big <= arr.size()) {big *= 2;} big /= 2;
      |           ~~~~^~~~~~~~~~~~~
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     while(arr.size() < (1 << pow2)) {
      |           ~~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp:69:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = arr.size() - small; i < arr.size(); i ++) {
      |                                     ~~^~~~~~~~~~~~
doll.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < pairs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~~~
doll.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < pairs.size(); i ++) {
      |                    ~~^~~~~~~~~~~~~~
doll.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < x.size(); i ++) {
      |                    ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 51 ms 5836 KB Output is correct
3 Correct 53 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 89 ms 7440 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 51 ms 5836 KB Output is correct
3 Correct 53 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 89 ms 7440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 87 ms 8492 KB Output is correct
9 Correct 89 ms 9136 KB Output is correct
10 Correct 138 ms 11976 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 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 51 ms 5836 KB Output is correct
3 Correct 53 ms 4916 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 89 ms 7440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 87 ms 8492 KB Output is correct
9 Correct 89 ms 9136 KB Output is correct
10 Correct 138 ms 11976 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 152 ms 11340 KB Output is correct
15 Correct 78 ms 7656 KB Output is correct
16 Correct 123 ms 10624 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 134 ms 11420 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 2 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 80 ms 6804 KB Output is correct
3 Correct 97 ms 6716 KB Output is correct
4 Correct 122 ms 9656 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 80 ms 6804 KB Output is correct
3 Correct 97 ms 6716 KB Output is correct
4 Correct 122 ms 9656 KB Output is correct
5 Correct 127 ms 10492 KB Output is correct
6 Correct 153 ms 10144 KB Output is correct
7 Correct 141 ms 10160 KB Output is correct
8 Correct 144 ms 9952 KB Output is correct
9 Correct 79 ms 6720 KB Output is correct
10 Correct 123 ms 9840 KB Output is correct
11 Correct 143 ms 9708 KB Output is correct
12 Correct 83 ms 6720 KB Output is correct
13 Correct 76 ms 6968 KB Output is correct
14 Correct 78 ms 7000 KB Output is correct
15 Correct 83 ms 7208 KB Output is correct
16 Correct 5 ms 544 KB Output is correct
17 Correct 98 ms 6196 KB Output is correct
18 Correct 116 ms 6684 KB Output is correct
19 Correct 73 ms 6708 KB Output is correct
20 Correct 128 ms 9836 KB Output is correct
21 Correct 125 ms 9660 KB Output is correct
22 Correct 119 ms 9696 KB Output is correct