oj.uz

Submission #301180

# Submission time Handle Problem Language Result Execution time Memory
301180 2020-09-17T17:24:43 Z TMJN Mechanical Doll (IOI18_doll) C++17
100 / 100
 378 ms 13028 KB 
    #include <bits/stdc++.h>
    #include "doll.h"
     
    #pragma GCC optimize("O0")
     
    using namespace std;
     
    int n, m, c = -2;
    vector<int> X, Y, mode;
     
    void b(int u, int l, int &j){
    	if(l){
    		Y[-u-1] = c;
    		b(c--, l-1, j);
    		if(j){
    			X[-u-1] = c;
    			b(c--, l-1, j);
    		}
    		else X[-u-1] = -1;
    	}
    	else{
    		Y[-u-1] = m+1, j--;
    		if(j) X[-u-1] = m+1, j--;
    		else X[-u-1] = -1;
    	}
    }
     
    void asg(int u, int t){
    	if(mode[-u-1]){
    		mode[-u-1] = 0;
    		if(Y[-u-1] == m+1) Y[-u-1] = t;
    		else asg(Y[-u-1], t);
    	}
    	else{
    		mode[-u-1] = 1;
    		if(X[-u-1] == m+1) X[-u-1] = t;
    		else asg(X[-u-1], t);
    	}
    }
     
    void create_circuit(int M, vector<int> A){
      auto K=A;
    	A.push_back(0);
    	n = A.size(), m = M;
    	vector<int> C(m+1);
    	X.resize(2*n), Y.resize(2*n), mode.resize(2*n);
    	C[0] = -1;
    	for(int i = 1; i <= m; i++) C[i] = -1;
    	int l = ceil(log2(n)), t = n;
    	b(-1, l-1, t);
    	for(int i = 0; i < n; i++) asg(-1, A[i]);
    	X.resize(-c-1), Y.resize(-c-1);
      	vector<bool>B(400000,false);
	int p=0;
	vector<int>T;
	int cnt=0;
	do{
		cnt++;
		if(p>=0){
			if(p)T.push_back(p);
			p=C[p];
		}
		else{
			if(B[-p-1]){
				B[-p-1]=!B[-p-1];
				p=Y[-p-1];
			}
			else{
				B[-p-1]=!B[-p-1];
				p=X[-p-1];
			}
		}
	}while(p);
	assert(K==T);
	bool f=false;
	for(int i=0;i<400000;i++){
		f|=B[i];
	}
	assert(!f);
	for(int i:C){
		assert(-(int)X.size()<=i&&i<=M);
	}
	for(int i:X){
		assert(-(int)X.size()<=i&&i<=M);
	}
	for(int i:Y){
		assert(-(int)X.size()<=i&&i<=M);
	}
	assert(cnt<=20000000);
    	answer(C, X, Y);
    }

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 143 ms 5308 KB Output is correct
3 Correct 128 ms 4868 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 20 ms 1484 KB Output is correct
6 Correct 168 ms 7456 KB Output is correct
7 Correct 4 ms 332 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 143 ms 5308 KB Output is correct
3 Correct 128 ms 4868 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 20 ms 1484 KB Output is correct
6 Correct 168 ms 7456 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 231 ms 9412 KB Output is correct
9 Correct 234 ms 9136 KB Output is correct
10 Correct 357 ms 13028 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 3 ms 332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 143 ms 5308 KB Output is correct
3 Correct 128 ms 4868 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 20 ms 1484 KB Output is correct
6 Correct 168 ms 7456 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 231 ms 9412 KB Output is correct
9 Correct 234 ms 9136 KB Output is correct
10 Correct 357 ms 13028 KB Output is correct
11 Correct 3 ms 332 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 360 ms 12512 KB Output is correct
15 Correct 231 ms 8044 KB Output is correct
16 Correct 338 ms 12392 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 326 ms 12788 KB Output is correct
21 Correct 4 ms 332 KB Output is correct
22 Correct 3 ms 332 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 246 ms 8220 KB Output is correct
3 Correct 223 ms 7484 KB Output is correct
4 Correct 314 ms 11304 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 246 ms 8220 KB Output is correct
3 Correct 223 ms 7484 KB Output is correct
4 Correct 314 ms 11304 KB Output is correct
5 Correct 344 ms 12176 KB Output is correct
6 Correct 337 ms 11764 KB Output is correct
7 Correct 350 ms 11880 KB Output is correct
8 Correct 341 ms 11704 KB Output is correct
9 Correct 214 ms 7500 KB Output is correct
10 Correct 334 ms 11492 KB Output is correct
11 Correct 352 ms 11284 KB Output is correct
12 Correct 214 ms 7488 KB Output is correct
13 Correct 241 ms 8684 KB Output is correct
14 Correct 223 ms 7932 KB Output is correct
15 Correct 219 ms 7988 KB Output is correct
16 Correct 12 ms 504 KB Output is correct
17 Correct 224 ms 8476 KB Output is correct
18 Correct 217 ms 8424 KB Output is correct
19 Correct 224 ms 7684 KB Output is correct
20 Correct 340 ms 11392 KB Output is correct
21 Correct 374 ms 11296 KB Output is correct
22 Correct 378 ms 11240 KB Output is correct