oj.uz

Submission #304603

# Submission time Handle Problem Language Result Execution time Memory
304603 2020-09-21T15:03:12 Z ryansee Mechanical Doll (IOI18_doll) C++14
100 / 100
 348 ms 43528 KB 
#include "doll.h"

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
vector<int> X, Y, jy;
ll lvl, co=-1;
struct node {
	int s,e,m;
	ll v,state;
	node*l,*r;
	node(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		v=0,state=0;
		if(s^e)l=new node(s,m),r=new node(m+1,e);
		else l=r=0;
	}
	void assign(int sz){
		if(sz<=0) return;
		if(s==e) {
			assert(sz==1);
			return;
		}
		int rs = e-m;
		r->assign(min(rs, sz));
		if(sz>rs) l->assign(sz-rs);
		else l=0;
	}
	ll trav() {
		if(s==e) {
			assert(v==0);
			v = jy.back(), jy.pop_back();
			return v;
		}
		if(v==0) {
			v = co --;
			X.eb(-1), Y.eb(-1);
		}
		if(state==0) state^=1, X[-v-1]=(!l?-1:(l->trav()));
		else state^=1, assert(r), Y[-v-1]=r->trav();
		return v;
	}
}*seg;
void create_circuit(int M, std::vector<int> A) {
	jy=A,jy.eb(0);
	vector<int> D(M+1,-1);
	DEC(i,25,0) if((1<<i) >= siz(jy)) lvl=i;
	seg=new node(1, 1<<lvl);
	seg->assign(siz(jy));
	reverse(all(jy));
	while(jy.size()) seg->trav();
	answer(D,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 89 ms 20492 KB Output is correct
3 Correct 113 ms 20808 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 10 ms 1356 KB Output is correct
6 Correct 135 ms 22652 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 89 ms 20492 KB Output is correct
3 Correct 113 ms 20808 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 10 ms 1356 KB Output is correct
6 Correct 135 ms 22652 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 234 ms 39892 KB Output is correct
9 Correct 211 ms 40388 KB Output is correct
10 Correct 329 ms 43528 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 89 ms 20492 KB Output is correct
3 Correct 113 ms 20808 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 10 ms 1356 KB Output is correct
6 Correct 135 ms 22652 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 234 ms 39892 KB Output is correct
9 Correct 211 ms 40388 KB Output is correct
10 Correct 329 ms 43528 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 266 ms 43044 KB Output is correct
15 Correct 263 ms 39404 KB Output is correct
16 Correct 348 ms 42788 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 297 ms 43192 KB Output is correct
21 Correct 2 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 204 ms 38396 KB Output is correct
3 Correct 224 ms 38440 KB Output is correct
4 Correct 276 ms 41244 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 204 ms 38396 KB Output is correct
3 Correct 224 ms 38440 KB Output is correct
4 Correct 276 ms 41244 KB Output is correct
5 Correct 342 ms 42524 KB Output is correct
6 Correct 319 ms 42296 KB Output is correct
7 Correct 314 ms 42352 KB Output is correct
8 Correct 275 ms 41972 KB Output is correct
9 Correct 224 ms 38392 KB Output is correct
10 Correct 273 ms 41940 KB Output is correct
11 Correct 284 ms 41552 KB Output is correct
12 Correct 205 ms 38668 KB Output is correct
13 Correct 186 ms 39024 KB Output is correct
14 Correct 178 ms 39108 KB Output is correct
15 Correct 182 ms 39264 KB Output is correct
16 Correct 4 ms 1484 KB Output is correct
17 Correct 191 ms 22688 KB Output is correct
18 Correct 207 ms 38628 KB Output is correct
19 Correct 211 ms 38648 KB Output is correct
20 Correct 312 ms 41872 KB Output is correct
21 Correct 319 ms 41636 KB Output is correct
22 Correct 313 ms 41652 KB Output is correct