oj.uz

Submission #696829

# Submission time Handle Problem Language Result Execution time Memory
696829 2023-02-07T11:10:07 Z whqkrtk04 Mechanical Doll (IOI18_doll) C++17
100 / 100
 109 ms 7948 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

void make(int &s, int cnt, int root, int idx, int lvl, vector<int> &X, vector<int> &Y) {
    if(lvl == 2) {
        if(cnt == 1) X[idx] = root;
        else X[idx] = INF;
        Y[idx] = INF;
    } else {
        if(cnt > lvl/2) {
            X[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, cnt-lvl/2, root, -X[idx]-1, lvl/2, X, Y);
            Y[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, lvl/2, root, -Y[idx]-1, lvl/2, X, Y);
        } else {
            X[idx] = root;
            Y[idx] = -(++s);
            X.push_back(0); Y.push_back(0);
            make(s, cnt, root, -Y[idx]-1, lvl/2, X, Y);
        }
    }
}

void solve(int &c, vector<int> &X, vector<int> &Y, vector<int> &nxt) {
    if(nxt.size() == 0) {
        c = 0;
    } else if(nxt.size() == 1) {
        c = nxt[0];
    } else {
        int s = 0;
        c = -(++s);
        X.push_back(0); Y.push_back(0);
        int lvl = 1;
        while(lvl < nxt.size()) lvl <<= 1;
        make(s, nxt.size(), c, -c-1, lvl, X, Y);
        int here = c, cnt = 0;
        vector<bool> chk(s+c+1, true);
        while(cnt < nxt.size()) {
            //cout << here << " " << c << "\n";
            int& there = (chk[-here+c] ? X[-here-1] : Y[-here-1]);
            chk[-here+c] = !chk[-here+c];
            if(there == INF) {
                there = nxt[cnt++];
                here = c;
            } else here = there;
        }
    }
}

void create_circuit(int M, vector<int> A) {
    vector<int> C(M+1, -1), X, Y;
    A.push_back(0);
    solve(C[0], X, Y, A);
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void solve(int&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
doll.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while(lvl < nxt.size()) lvl <<= 1;
      |               ~~~~^~~~~~~~~~~~
doll.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while(cnt < nxt.size()) {
      |               ~~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 3748 KB Output is correct
3 Correct 33 ms 3596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 50 ms 5016 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 3748 KB Output is correct
3 Correct 33 ms 3596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 50 ms 5016 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 67 ms 5180 KB Output is correct
9 Correct 70 ms 5588 KB Output is correct
10 Correct 102 ms 7948 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 36 ms 3748 KB Output is correct
3 Correct 33 ms 3596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 50 ms 5016 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 67 ms 5180 KB Output is correct
9 Correct 70 ms 5588 KB Output is correct
10 Correct 102 ms 7948 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 102 ms 7616 KB Output is correct
15 Correct 64 ms 4804 KB Output is correct
16 Correct 97 ms 7308 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 99 ms 7688 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 284 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 61 ms 4408 KB Output is correct
3 Correct 60 ms 4300 KB Output is correct
4 Correct 92 ms 6460 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 61 ms 4408 KB Output is correct
3 Correct 60 ms 4300 KB Output is correct
4 Correct 92 ms 6460 KB Output is correct
5 Correct 102 ms 7172 KB Output is correct
6 Correct 98 ms 7100 KB Output is correct
7 Correct 98 ms 7184 KB Output is correct
8 Correct 102 ms 6916 KB Output is correct
9 Correct 59 ms 4296 KB Output is correct
10 Correct 92 ms 6780 KB Output is correct
11 Correct 95 ms 6460 KB Output is correct
12 Correct 61 ms 4340 KB Output is correct
13 Correct 65 ms 4712 KB Output is correct
14 Correct 63 ms 4800 KB Output is correct
15 Correct 65 ms 4820 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 59 ms 5644 KB Output is correct
18 Correct 60 ms 4340 KB Output is correct
19 Correct 65 ms 4412 KB Output is correct
20 Correct 98 ms 6660 KB Output is correct
21 Correct 97 ms 6472 KB Output is correct
22 Correct 109 ms 6468 KB Output is correct