oj.uz

Submission #316833

# Submission time Handle Problem Language Result Execution time Memory
316833 2020-10-28T09:42:36 Z anakib1 Mechanical Doll (IOI18_doll) C++17
100 / 100
 158 ms 11824 KB 
//나는 가상 소녀들에게 큰 호감이 있습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <chrono>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <deque>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdarg.h>
#include <utility>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unisgned long long
#define ld long double
#define all(a) a.begin(), a.end()
#define SORT(a) sort(all(a))
#define pii pair<int, int>
#define tii triple<int, int, int>
#define e 1e-7
#define PI acos(-1)
#define sz(a) (int)(a.size())
#define inf 1e9
#define vi vector<int>
#define F first
#define S second
#define rng(x) for(int _ = 0; _ < (x); _++)
#define rngi(i, x) for(int i = 0; i < (x); i++)
#define rngsi(s, i, x) for(int i = (s); i <(x); i++)
#define problem "a"

template<typename A, typename B, typename C>
struct triple {
    A X;
    B Y;
    C Z;
    triple(A a = 0, B b = 0, C c = 0) :X(a), Y(b), Z(c) {}
};
template<typename A, typename B, typename C>
triple<A, B, C> make_triple(A a = 0, B b = 0, C c = 0) {
    return triple<A, B, C>(a, b, c);
}
template<typename A, typename B, typename C>
bool operator<(const triple<A, B, C>& a, const triple<A, B, C>& b) {
    if (a.X != b.X)
        return a.X < b.X;
    if (a.Y != b.Y)
        return a.Y < b.Y;
    return a.Z < b.Z;
}
template<typename T, typename SS>
ostream& operator<<(ostream& ofs, const pair<T, SS>& p) {
    ofs << "( " << p.F << " , " << p.S << " )";
    return ofs;
}
template<typename T>
void print(T a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
template<typename T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}
template<typename T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}
template<typename T, typename D>
D min(T a) {
    return *min_element(all(a));
}
template<typename T, typename D>
D max(T a) {
    return *max_element(all(a));
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
}; 

#include "doll.h"
int state[700707];
int sz = 1, n;
int get(int v) {
    if (v >= sz) return (sz - n <= v - sz)? v - sz:inf;
    state[v] ^= 1;
    if (state[v])return get(v << 1); return get(v << 1 | 1);
}
void create_circuit(int m, std::vector<int> a) {
    a.push_back(0);
    n = sz(a);
    while (sz < n) sz <<= 1;
    vi t(sz << 1);
    rngi(i, sz)t[sz + i] = inf;
    int tt = 0;
    vi rev(sz);
    rngi(i, sz) rev[i] = get(1);
    int j = 0; rngi(i, sz) if (rev[i] != inf) { t[rev[i] + sz] = a[j], j++; }
    vi x, y;
    for (int i = sz - 1; i > 0; i--) {
        if (t[i << 1] == t[i << 1 | 1] && t[i << 1] == inf)t[i] = inf;
        else {
            t[i] = --tt;
            x.push_back(t[i << 1]);
            y.push_back(t[i << 1 | 1]);
        }
    }
    rngi(i, sz(x)) {
        if (x[i] == inf) x[i] = tt;
        if (y[i] == inf) y[i] = tt;
    }
    answer(vi(m + 1, tt), x, y);
}

Compilation message

doll.cpp: In function 'int get(int)':
doll.cpp:119:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  119 |     if (state[v])return get(v << 1); return get(v << 1 | 1);
      |     ^~
doll.cpp:119:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  119 |     if (state[v])return get(v << 1); return get(v << 1 | 1);
      |                                      ^~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 50 ms 5708 KB Output is correct
3 Correct 50 ms 5428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1092 KB Output is correct
6 Correct 66 ms 6664 KB Output is correct
7 Correct 2 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 50 ms 5708 KB Output is correct
3 Correct 50 ms 5428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1092 KB Output is correct
6 Correct 66 ms 6664 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 129 ms 9216 KB Output is correct
9 Correct 106 ms 9616 KB Output is correct
10 Correct 133 ms 11744 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 50 ms 5708 KB Output is correct
3 Correct 50 ms 5428 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1092 KB Output is correct
6 Correct 66 ms 6664 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 129 ms 9216 KB Output is correct
9 Correct 106 ms 9616 KB Output is correct
10 Correct 133 ms 11744 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 158 ms 11544 KB Output is correct
15 Correct 89 ms 9192 KB Output is correct
16 Correct 121 ms 11488 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 118 ms 11824 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 2 ms 204 KB Output is correct
2 Correct 2 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 2 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 96 ms 8664 KB Output is correct
3 Correct 85 ms 8688 KB Output is correct
4 Correct 118 ms 10920 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 96 ms 8664 KB Output is correct
3 Correct 85 ms 8688 KB Output is correct
4 Correct 118 ms 10920 KB Output is correct
5 Correct 119 ms 11220 KB Output is correct
6 Correct 117 ms 11060 KB Output is correct
7 Correct 115 ms 11092 KB Output is correct
8 Correct 128 ms 11024 KB Output is correct
9 Correct 120 ms 8684 KB Output is correct
10 Correct 148 ms 11040 KB Output is correct
11 Correct 109 ms 10924 KB Output is correct
12 Correct 87 ms 8700 KB Output is correct
13 Correct 107 ms 8808 KB Output is correct
14 Correct 93 ms 8812 KB Output is correct
15 Correct 104 ms 8800 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 87 ms 6708 KB Output is correct
18 Correct 112 ms 8424 KB Output is correct
19 Correct 82 ms 8428 KB Output is correct
20 Correct 126 ms 10668 KB Output is correct
21 Correct 111 ms 10672 KB Output is correct
22 Correct 110 ms 10676 KB Output is correct