oj.uz

Submission #101674

# Submission time Handle Problem Language Result Execution time Memory
101674 2019-03-19T08:28:16 Z briansu Mechanical Doll (IOI18_doll) C++14
100 / 100
 169 ms 11056 KB 
#include "doll.h"
//{
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}

const ll MAXn = 400000 + 5;

ll x[MAXn], y[MAXn], stat[MAXn];
vector<int> C, X, Y;
ll sit = 0;


inline ll nnd(){
  return --sit;
}

void build(int &now, int sz)
{
  if(sz == 1)
  {
    now = MAXn;
    return;
  }
  now = nnd();
  assert(sz % 2 == 0);
  build(x[-now-1], sz>>1);
  build(y[-now-1], sz>>1);
}

void create_circuit(int M, std::vector<int> A) {
  X.clear();Y.clear();C.clear();sit = 0;
  if(SZ(A) == 1)
  {
    vector<int> tmp;
    REP(i, M+1)tmp.pb(0);
    tmp[0] = A[0];
    answer(tmp, vector<int>(), vector<int>());
    return;
  }
  vector<int> v;
  for(int i = 1;i < SZ(A);i ++)v.pb(A[i]);
  int rt;
  rt = nnd();

  for(int i = __lg(SZ(v)), now = rt;i >= 0;i --)
  {
    if(SZ(v) & (1<<i))build(x[-now-1], (1<<i));
    else x[-now-1] = rt;
    if(i != 0)now = y[-now-1] = nnd();
    else y[-now-1] = 0;
  }

  debug(v);
  ll now = rt, it = 0;
  REP(i, -sit)stat[i] = 0;
  while(now != 0)
  {
    if(stat[-now-1] == 0){ // x
      stat[-now-1] ^= 1;
      if(x[-now-1] == MAXn){
        assert(it != SZ(v));
        x[-now-1] = v[it++];
        now = rt;
      }else now = x[-now-1];
    }
    else{ // y
      stat[-now-1] ^= 1;
      if(y[-now-1] == MAXn){
        assert(it != SZ(v));
        y[-now-1] = v[it++];
        now = rt;
      }else now = y[-now-1];
    }
  }
  
  //build(rt, v);
  C.pb(A[0]);
  REP(i, M)C.pb(rt);
  REP(i, -sit)X.pb(x[i]), Y.pb(y[i]);
  answer(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 55 ms 4804 KB Output is correct
3 Correct 46 ms 4844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6260 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 55 ms 4804 KB Output is correct
3 Correct 46 ms 4844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6260 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 7232 KB Output is correct
9 Correct 118 ms 8628 KB Output is correct
10 Correct 168 ms 10892 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 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 55 ms 4804 KB Output is correct
3 Correct 46 ms 4844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 12 ms 1604 KB Output is correct
6 Correct 68 ms 6260 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 90 ms 7232 KB Output is correct
9 Correct 118 ms 8628 KB Output is correct
10 Correct 168 ms 10892 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 141 ms 10644 KB Output is correct
15 Correct 85 ms 8240 KB Output is correct
16 Correct 130 ms 11056 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 136 ms 10804 KB Output is correct
21 Correct 1 ms 292 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 2 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 72 ms 6820 KB Output is correct
3 Correct 79 ms 6620 KB Output is correct
4 Correct 119 ms 9816 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 72 ms 6820 KB Output is correct
3 Correct 79 ms 6620 KB Output is correct
4 Correct 119 ms 9816 KB Output is correct
5 Correct 134 ms 10884 KB Output is correct
6 Correct 123 ms 9944 KB Output is correct
7 Correct 123 ms 9976 KB Output is correct
8 Correct 169 ms 10216 KB Output is correct
9 Correct 81 ms 6592 KB Output is correct
10 Correct 144 ms 9784 KB Output is correct
11 Correct 138 ms 9788 KB Output is correct
12 Correct 84 ms 6836 KB Output is correct
13 Correct 79 ms 6940 KB Output is correct
14 Correct 96 ms 7364 KB Output is correct
15 Correct 94 ms 7476 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 86 ms 6720 KB Output is correct
18 Correct 75 ms 6716 KB Output is correct
19 Correct 79 ms 6876 KB Output is correct
20 Correct 133 ms 9992 KB Output is correct
21 Correct 131 ms 9820 KB Output is correct
22 Correct 131 ms 9780 KB Output is correct