oj.uz

Submission #76226

# Submission time Handle Problem Language Result Execution time Memory
76226 2018-09-12T12:35:13 Z born2rule Mechanical Doll (IOI18_doll) C++14
84 / 100
 179 ms 12312 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 v[N],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);
  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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 51 ms 8496 KB Output is correct
3 Correct 55 ms 8728 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 18 ms 6092 KB Output is correct
6 Correct 76 ms 9616 KB Output is correct
7 Runtime error 12 ms 9876 KB Execution killed with signal 11

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 51 ms 8496 KB Output is correct
3 Correct 55 ms 8728 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 18 ms 6092 KB Output is correct
6 Correct 76 ms 9616 KB Output is correct
7 Runtime error 12 ms 9876 KB Execution killed with signal 11

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4940 KB Output is correct
2 Correct 51 ms 8496 KB Output is correct
3 Correct 55 ms 8728 KB Output is correct
4 Correct 6 ms 4940 KB Output is correct
5 Correct 18 ms 6092 KB Output is correct
6 Correct 76 ms 9616 KB Output is correct
7 Runtime error 12 ms 9876 KB Execution killed with signal 11

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 7 ms 4940 KB Output is correct
4 Correct 5 ms 4924 KB Output is correct
5 Correct 7 ms 4936 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 5 ms 4940 KB Output is correct
8 Correct 5 ms 4940 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 81 ms 9404 KB Output is correct
3 Correct 86 ms 9904 KB Output is correct
4 Correct 128 ms 11624 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 81 ms 9404 KB Output is correct
3 Correct 86 ms 9904 KB Output is correct
4 Correct 128 ms 11624 KB Output is correct
5 Correct 179 ms 12312 KB Output is correct
6 Correct 133 ms 12032 KB Output is correct
7 Correct 139 ms 12124 KB Output is correct
8 Correct 153 ms 11828 KB Output is correct
9 Correct 95 ms 9848 KB Output is correct
10 Correct 130 ms 11828 KB Output is correct
11 Correct 134 ms 11624 KB Output is correct
12 Correct 94 ms 10096 KB Output is correct
13 Correct 114 ms 9588 KB Output is correct
14 Correct 91 ms 10624 KB Output is correct
15 Correct 129 ms 10676 KB Output is correct
16 Correct 8 ms 5068 KB Output is correct
17 Correct 85 ms 9472 KB Output is correct
18 Correct 88 ms 9452 KB Output is correct
19 Correct 90 ms 10164 KB Output is correct
20 Correct 133 ms 11692 KB Output is correct
21 Correct 132 ms 11636 KB Output is correct
22 Correct 134 ms 11616 KB Output is correct