oj.uz

Submission #119870

# Submission time Handle Problem Language Result Execution time Memory
119870 2019-06-22T14:19:55 Z Meloric Mechanical Doll (IOI18_doll) C++14
100 / 100
 313 ms 100660 KB 
#include "doll.h"
#include <bits/stdc++.h>

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;

struct sw{
    int fi, se, flag;
    vector<int> pos1, pos2;
};
vector<sw> tree;
vector<pair<int, pii>> srt;
vector<int> psums;

int dec(vector<int>& a){
    int ans = 0; int pw = 1;
    for(int i = 0; i < a.size(); i++){
        ans+=a[i]*pw; pw*=2;
    }
    return ans;
}
void build(int v, vector<int> pos){
    if(v>=tree.size())return;
    tree[v].pos1 = pos; tree[v].pos1.pb(0);
    tree[v].pos2 = pos; tree[v].pos2.pb(1);
    build(v*2, tree[v].pos1);
    build(v*2+1, tree[v].pos2);
}
void create_circuit(int m, vector<int> A) {
    int n = A.size();
    vector<int> C; C.assign(m+1, -1);
    int len = 1; int lvl = 2;
    while(1){
        if(lvl >= n+1)break;
        len+=lvl;
        lvl*=2;
    }
    tree.assign(len+1, {-1, -1, 1, {}, {}});
    build(1, {});
    psums.assign(len+1, 1); psums[0] = 0;
    for(int i = 0; i < n+1; i++){
        int id = tree.size()-1-(i/2);
        if(i%2)srt.pb({dec(tree[id].pos1), {id, 1}});
        else srt.pb({dec(tree[id].pos2), {id, 2}});
    }
    A.pb(0);
    sort(srt.begin(), srt.end());
    int j = 0;
    /*
    cout << srt.size() << 's';
    for(auto i : A){
        cout << i << ' ';
    }*/
    for(auto i : srt){
        int id = i.Y.X; int fi = i.Y.Y == 1;
        if(fi){
            tree[id].fi = A[j];
        }else{
            tree[id].se = A[j];
        }
        tree[id].flag = 0;
        j++;
    }
    /*
    for(auto i : tree){
        cout << i.fi <<' '<<i.se<<' '<<i.flag<<'\n';
    }*/
    for(int i = tree.size()-1; i>1; i--){
        if(tree[i].flag)psums[i]=0;
        else tree[i/2].flag = tree[i].flag;
    }/*
    for(auto i : psums)cout << i << ' ';
    cout << '\n';*/
    for(int i = 1; i< len+1; i++){
        psums[i]+=psums[i-1];
    }/*
    for(auto i : psums)cout << i << ' ';
    cout << '\n';*/
    for(int i = tree.size()-1; i > 1; i--){
        if(tree[i].flag)continue;
        if(i%2){
            tree[i/2].se = -psums[i];
        }else{
            tree[i/2].fi = -psums[i];
        }
    }
    vector<int> Xe, Ye;
    for(int i = 1; i< tree.size(); i++){
        if(tree[i].flag)continue;
        Xe.pb(tree[i].fi);
        Ye.pb(tree[i].se);
    }
    answer(C, Xe, Ye);
}

Compilation message

doll.cpp: In function 'int dec(std::vector<int>&)':
doll.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
doll.cpp: In function 'void build(int, std::vector<int>)':
doll.cpp:27:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(v>=tree.size())return;
      |        ~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sw>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 1; i< tree.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 136 ms 48272 KB Output is correct
3 Correct 116 ms 47904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 140 ms 49928 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 136 ms 48272 KB Output is correct
3 Correct 116 ms 47904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 140 ms 49928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 241 ms 97156 KB Output is correct
9 Correct 260 ms 97588 KB Output is correct
10 Correct 283 ms 100660 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 136 ms 48272 KB Output is correct
3 Correct 116 ms 47904 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 11 ms 1356 KB Output is correct
6 Correct 140 ms 49928 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 241 ms 97156 KB Output is correct
9 Correct 260 ms 97588 KB Output is correct
10 Correct 283 ms 100660 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 307 ms 100116 KB Output is correct
15 Correct 238 ms 96644 KB Output is correct
16 Correct 313 ms 100032 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 281 ms 100468 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 2 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 229 ms 96016 KB Output is correct
3 Correct 222 ms 96032 KB Output is correct
4 Correct 283 ms 99316 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 229 ms 96016 KB Output is correct
3 Correct 222 ms 96032 KB Output is correct
4 Correct 283 ms 99316 KB Output is correct
5 Correct 272 ms 100080 KB Output is correct
6 Correct 266 ms 99988 KB Output is correct
7 Correct 283 ms 100100 KB Output is correct
8 Correct 312 ms 99780 KB Output is correct
9 Correct 256 ms 96052 KB Output is correct
10 Correct 262 ms 99732 KB Output is correct
11 Correct 275 ms 99524 KB Output is correct
12 Correct 224 ms 96300 KB Output is correct
13 Correct 229 ms 96504 KB Output is correct
14 Correct 226 ms 96568 KB Output is correct
15 Correct 258 ms 96704 KB Output is correct
16 Correct 8 ms 2636 KB Output is correct
17 Correct 146 ms 50100 KB Output is correct
18 Correct 222 ms 96204 KB Output is correct
19 Correct 228 ms 96268 KB Output is correct
20 Correct 296 ms 99680 KB Output is correct
21 Correct 294 ms 99508 KB Output is correct
22 Correct 305 ms 99604 KB Output is correct