oj.uz

Submission #290054

# Submission time Handle Problem Language Result Execution time Memory
290054 2020-09-03T10:37:13 Z dandrozavr Mechanical Doll (IOI18_doll) C++14
39 / 100
 252 ms 25980 KB 
#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define _ <<" "<<
#define pii pair < int , int >

using namespace std;

struct seg_tree{
    vector < int > t, num;
    vector < bool > l, r;
    int n, len, how = 1, bad = 0;
    seg_tree(){n = len = 0;};
    seg_tree(int _n){
        n = _n;
        len = 1;
        while(len <= n) len <<= 1;
        t.resize(len << 1 | 1);
        l.resize(len << 1 | 1);
        r.resize(len << 1 | 1);
        num.resize(len << 1 | 1);
        for (int i = 0; i < num.size(); ++i)
            num[i] = i;
    };

    void way(int v, int tl, int tr){
        if (!t[v]){
            t[v] = 2;
        } else
        if (t[v] == 1) t[v] = 2; else t[v] = 1;
        if (tl == tr){
            t[v] = how++;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (t[v] == 1){
            way(v << 1, tl, tm);
            l[v] = 1;
        }else{
            way(v << 1 | 1, tm + 1, tr);
            r[v] = 1;
        }
    }
};

void create_circuit (int m, vector < int > a) {
    int n = a.size();
    a.pb(0);
    vector < int > c;
    vector < int > g[m + 1];
    for (int i = 1; i <= n; ++i){
        g[a[i - 1]].pb(a[i]);
    }
    g[0].pb(a[0]);
    int now = 1;
    vector < pii > swit;
    for (int i = 0; i <= m; ++i){
        int sz = g[i].size();
        if (!sz){
            c.pb(0);
            continue;
        }
        if (sz == 1){
            c.pb(g[i][0]);
        } else {
            vector < int > all;
            for (int j = 0; j < sz; ++j) all.pb(g[i][j]);
            seg_tree t;
            t = seg_tree(sz);
            int cnt = 0;
            for (int i = 0; i < sz; ++i){
                t.way(1, 0, t.len - 1);
            }
            vector < int > vis;
            vector < int > q;
            reverse(all.begin(), all.end());
            for (int i = t.t.size() - 1; i >= 1; --i)
                if (t.t[i]){
                    if (!t.r[i]){
                        t.num[i] = -all[t.t[i] - 1];
                        continue;
                    }
                    if (!t.l[i])
                        t.num[i << 1] = 1;
                    vis.pb(i);
                    q.pb(i);
                    if (t.num[i << 1] > 0) q.pb(t.num[i << 1]);
                    if (t.num[i << 1 | 1] > 0) q.pb(t.num[i << 1 | 1]);
                }
            sort(q.begin(), q.end());
            q.resize(unique(q.begin(), q.end()) - q.begin());
            unordered_map < int , int > mp;
            reverse(vis.begin(), vis.end());
            for (int i : q) mp[i] = now++;
            for (int i : vis){
                int f = t.num[i << 1];
                if (mp.count(f)) f = mp[f];
                int s = t.num[i << 1 | 1];
                if (mp.count(s)) s = mp[s];
                swit.pb({-f, -s});
//                cout << i _ -f _ -s << endl;
            }
//            cout << vis.size() _ now << endl;
//            for (int i = 1; i < t.num.size(); ++i)
//                cout << t.num[i] _ t.t[i] _ t.l[i] _ t.r[i] << endl;
//            for (auto i : swit)
//                cout << i.F _ i.S << endl;
            c.pb(-mp[t.num[1]]);
        }
    }
//    for (int i : c) cout << i << " ";
//    cout << endl;
    vector < int > X, Y;
    for (int i = 0; i < swit.size(); ++i){
        X.pb(swit[i].F), Y.pb(swit[i].S);
//        cout << X.back() _ Y.back() << endl;
    }
    answer(c, X, Y);
}

Compilation message

doll.cpp: In constructor 'seg_tree::seg_tree(int)':
doll.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0; i < num.size(); ++i)
      |                         ~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:76:17: warning: unused variable 'cnt' [-Wunused-variable]
   76 |             int cnt = 0;
      |                 ^~~
doll.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < swit.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 39 ms 6460 KB Output is correct
3 Correct 28 ms 5172 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3908 KB Output is correct
6 Correct 46 ms 7624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 6460 KB Output is correct
3 Correct 28 ms 5172 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3908 KB Output is correct
6 Correct 46 ms 7624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 151 ms 13744 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 39 ms 6460 KB Output is correct
3 Correct 28 ms 5172 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3908 KB Output is correct
6 Correct 46 ms 7624 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 151 ms 13744 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 187 ms 25140 KB Output is partially correct
3 Partially correct 185 ms 25188 KB Output is partially correct
4 Partially correct 207 ms 25980 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Partially correct 187 ms 25140 KB Output is partially correct
3 Partially correct 185 ms 25188 KB Output is partially correct
4 Partially correct 207 ms 25980 KB Output is partially correct
5 Partially correct 212 ms 15916 KB Output is partially correct
6 Partially correct 206 ms 17368 KB Output is partially correct
7 Partially correct 222 ms 17004 KB Output is partially correct
8 Partially correct 225 ms 18532 KB Output is partially correct
9 Partially correct 178 ms 17996 KB Output is partially correct
10 Partially correct 252 ms 19772 KB Output is partially correct
11 Partially correct 216 ms 19696 KB Output is partially correct
12 Partially correct 144 ms 11884 KB Output is partially correct
13 Partially correct 143 ms 11688 KB Output is partially correct
14 Partially correct 136 ms 11060 KB Output is partially correct
15 Partially correct 128 ms 10760 KB Output is partially correct
16 Partially correct 5 ms 588 KB Output is partially correct
17 Partially correct 123 ms 9748 KB Output is partially correct
18 Partially correct 128 ms 9632 KB Output is partially correct
19 Partially correct 137 ms 10412 KB Output is partially correct
20 Partially correct 177 ms 13196 KB Output is partially correct
21 Partially correct 201 ms 15700 KB Output is partially correct
22 Partially correct 157 ms 11676 KB Output is partially correct