oj.uz

Submission #112975

# Submission time Handle Problem Language Result Execution time Memory
112975 2019-05-23T00:17:23 Z Benq Mechanical Doll (IOI18_doll) C++14
100 / 100
 231 ms 20004 KB 
#include "doll.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 200005;
const ld PI = 4*atan((ld)1);

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);

    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) { 
        re(first); re(rest...); 
    }

    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T, size_t SZ> void pr(const array<T,SZ>& x);
    template<class T> void pr(const vector<T>& x);
    template<class T> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);

    template<class T> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { 
        pr(first); pr(rest...); 
    }

    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void prContain(const T& x) {
        pr("{");
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
        pr("}");
    }
    template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    template<class T> void pr(const vector<T>& x) { prContain(x); }
    template<class T> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
    
    void ps() { pr("\n"); }
    template<class Arg> void ps(const Arg& first) { 
        pr(first); ps(); // no space at end of line
    }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { 
        pr(first," "); ps(rest...); // print w/ spaces
    }
}

using namespace output;

vi A;
int N, M, cur = -1;
vi X, Y;
int po2 = 0;

int divi(int l, int r) {
    if (r < (1<<po2)-N) return -1;
    if (l == r) {
        int z = 0; F0Rd(i,po2) if (l&(1<<i)) z ^= 1<<(po2-1-i);
        return z;
    }
    int ind = cur--; X.pb(MOD), Y.pb(MOD);
    int m = (l+r)/2; int a = divi(l,m), b = divi(m+1,r);
    X[-ind-1] = a, Y[-ind-1] = b;
    return ind;
}

void create_circuit(int _M, std::vector<int> _A) {
  A = _A; A.pb(0); N = A.size();  M = _M; 
  while ((1<<po2) < sz(A)) po2 ++;
  vi C(M+1,-1); divi(0,(1<<po2)-1); 
  map<int,int> m;
  trav(t,X) if (t >= 0) m[t] = 0;
  trav(t,Y) if (t >= 0) m[t] = 0;
  assert(sz(m) == N);
  int co = 0;
  trav(t,m) t.s = A[co++];
  trav(t,X) if (t >= 0) t = m[t];
  trav(t,Y) if (t >= 0) t = m[t];
  answer(C,X,Y);
  // ps(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 66 ms 7136 KB Output is correct
3 Correct 75 ms 7452 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 105 ms 10988 KB Output is correct
7 Correct 1 ms 256 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 66 ms 7136 KB Output is correct
3 Correct 75 ms 7452 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 105 ms 10988 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 125 ms 13180 KB Output is correct
9 Correct 142 ms 13640 KB Output is correct
10 Correct 231 ms 20004 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 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 66 ms 7136 KB Output is correct
3 Correct 75 ms 7452 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 1356 KB Output is correct
6 Correct 105 ms 10988 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 125 ms 13180 KB Output is correct
9 Correct 142 ms 13640 KB Output is correct
10 Correct 231 ms 20004 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 218 ms 19536 KB Output is correct
15 Correct 148 ms 12684 KB Output is correct
16 Correct 188 ms 19348 KB Output is correct
17 Correct 2 ms 208 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 204 ms 19792 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 2 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 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 101 ms 11756 KB Output is correct
3 Correct 127 ms 11712 KB Output is correct
4 Correct 190 ms 17748 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 101 ms 11756 KB Output is correct
3 Correct 127 ms 11712 KB Output is correct
4 Correct 190 ms 17748 KB Output is correct
5 Correct 177 ms 19236 KB Output is correct
6 Correct 221 ms 18864 KB Output is correct
7 Correct 197 ms 18988 KB Output is correct
8 Correct 175 ms 18620 KB Output is correct
9 Correct 113 ms 11752 KB Output is correct
10 Correct 208 ms 18556 KB Output is correct
11 Correct 207 ms 18108 KB Output is correct
12 Correct 112 ms 12008 KB Output is correct
13 Correct 106 ms 12332 KB Output is correct
14 Correct 132 ms 12428 KB Output is correct
15 Correct 117 ms 12516 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 118 ms 11972 KB Output is correct
18 Correct 118 ms 12084 KB Output is correct
19 Correct 108 ms 11948 KB Output is correct
20 Correct 187 ms 18468 KB Output is correct
21 Correct 173 ms 18128 KB Output is correct
22 Correct 210 ms 18228 KB Output is correct