oj.uz

Submission #76230

# Submission time Handle Problem Language Result Execution time Memory
76230 2018-09-12T12:40:04 Z born2rule Mechanical Doll (IOI18_doll) C++14
100 / 100
 152 ms 8448 KB 
#include <bits/stdc++.h>
#include "doll.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=200005;
vi X,Y;
int cnt=0,p=1,n;
bool state[N*10];
int build(int low,int high)
{
  if(low>=high) return 0;
  if(high<p-n) return -1;
  int mid=(low+high)>>1;
  int ind=++cnt;
  X.pb(0); Y.pb(0);
  int x=build(low,mid),y=build(mid+1,high);
  X[ind-1]=x;
  Y[ind-1]=y;
  return -ind;
}
void solve(int ind,int nxt)
{
  int &curr=((state[-ind])?Y[-ind-1]:X[-ind-1]);
  state[-ind]=!state[-ind];
  if(curr==0) curr=nxt;
  else solve(curr,nxt);
}
void create_circuit(int m,vi A)
{
  n=sz(A);
  if(n==1)
    {
      vi C(m+1,0);
      C[0]=A[0];
      return answer(C,X,Y);
    }
  while(p<n) p<<=1;
  build(0,p-1);
  rep(i,1,n) solve(-1,A[i]);
  if(n&1) solve(-1,-1);
  solve(-1,0);
  vi C(m+1,-1);
  C[0]=A[0];
  answer(C,X,Y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 51 ms 3792 KB Output is correct
3 Correct 51 ms 3932 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1484 KB Output is correct
6 Correct 74 ms 4884 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 2 ms 204 KB Output is correct
2 Correct 51 ms 3792 KB Output is correct
3 Correct 51 ms 3932 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1484 KB Output is correct
6 Correct 74 ms 4884 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 98 ms 5572 KB Output is correct
9 Correct 96 ms 7212 KB Output is correct
10 Correct 137 ms 8448 KB Output is correct
11 Correct 1 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 2 ms 204 KB Output is correct
2 Correct 51 ms 3792 KB Output is correct
3 Correct 51 ms 3932 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 15 ms 1484 KB Output is correct
6 Correct 74 ms 4884 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 98 ms 5572 KB Output is correct
9 Correct 96 ms 7212 KB Output is correct
10 Correct 137 ms 8448 KB Output is correct
11 Correct 1 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 142 ms 8056 KB Output is correct
15 Correct 88 ms 6164 KB Output is correct
16 Correct 133 ms 7712 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 135 ms 8220 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 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 93 ms 4648 KB Output is correct
3 Correct 81 ms 5144 KB Output is correct
4 Correct 152 ms 6948 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 93 ms 4648 KB Output is correct
3 Correct 81 ms 5144 KB Output is correct
4 Correct 152 ms 6948 KB Output is correct
5 Correct 133 ms 7660 KB Output is correct
6 Correct 132 ms 7256 KB Output is correct
7 Correct 136 ms 7424 KB Output is correct
8 Correct 132 ms 7128 KB Output is correct
9 Correct 110 ms 5164 KB Output is correct
10 Correct 125 ms 7132 KB Output is correct
11 Correct 129 ms 6956 KB Output is correct
12 Correct 81 ms 5408 KB Output is correct
13 Correct 110 ms 4784 KB Output is correct
14 Correct 87 ms 5900 KB Output is correct
15 Correct 88 ms 6028 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 80 ms 4764 KB Output is correct
18 Correct 77 ms 4664 KB Output is correct
19 Correct 87 ms 5400 KB Output is correct
20 Correct 129 ms 7012 KB Output is correct
21 Correct 139 ms 6960 KB Output is correct
22 Correct 125 ms 6960 KB Output is correct