oj.uz

Submission #295438

# Submission time Handle Problem Language Result Execution time Memory
295438 2020-09-09T16:43:08 Z shayan_p Mechanical Doll (IOI18_doll) C++17
100 / 100
 171 ms 14980 KB 
#include<bits/stdc++.h>
#include "doll.h"
     
#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
     
using namespace std;
     
typedef pair<int, int> pii;
typedef long long ll;
     
const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
 
vector<pii> vec;
int what[maxn]; // maxn
int arr[maxn];
 
void solve(vector<int> inp, int lg, int rt){
    assert(!vec.empty());
    if(lg == 1){
	if(sz(inp) == 2)
	    vec[-rt-1] = {inp[0], inp[1]};
	else
	    vec[-rt-1] = {-1, inp[0]};
	return;
    }
    reverse(inp.begin(), inp.end());
    vector<int> v1, v2;
    while(sz(inp) > (1<<(lg-1))){
	v1.PB(inp.back());
	inp.pop_back();
    }
    v2 = inp;
    reverse(v2.begin(), v2.end());
    if(v1.empty()){
	vec[-rt-1].F = -1;
    }
    else{
	vec.PB({-1, -1});
	int r = -sz(vec);
	vec[-rt-1].F = r;
	solve(v1, lg-1, r);
    }
    vec.PB({-1, -1});
    int r = -sz(vec);
    vec[-rt-1].S = r;
    solve(v2, lg-1, r);
}
 
void create_circuit(int M, vector<int> A) {
    A.PB(0);
    int N = sz(A);
    int extra = 0;
    while(__builtin_popcount(N + extra) != 1)
	extra++;
    vec.PB({-1, -1});
    int lg = __builtin_ctz(N + extra);
    for(int i = 0; i < (1<<lg); i++){
	for(int j = 0; j < lg; j++){
	    what[i]+= bit(i, j) << (lg-1-j);
	}
    }
    iota(arr, arr + N, 0);
    sort(arr, arr + N, [&](int i, int j){ return what[i + extra] < what[j + extra]; });
 
    vector<int> tdo(N);
    for(int i = 0; i < N; i++){
	tdo[arr[i]] = A[i];
    }
    solve(tdo, lg, -1);
    
    vector<int> C, X, Y;
    for(int i = 0; i <= M; i++){
    	C.PB(-1);
    }
    for(pii p : vec){
    	X.PB(p.F);
    	Y.PB(p.S);
    }
    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 56 ms 6816 KB Output is correct
3 Correct 61 ms 6180 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1604 KB Output is correct
6 Correct 106 ms 8324 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 56 ms 6816 KB Output is correct
3 Correct 61 ms 6180 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1604 KB Output is correct
6 Correct 106 ms 8324 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 10948 KB Output is correct
9 Correct 99 ms 10500 KB Output is correct
10 Correct 155 ms 14980 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 56 ms 6816 KB Output is correct
3 Correct 61 ms 6180 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 17 ms 1604 KB Output is correct
6 Correct 106 ms 8324 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 93 ms 10948 KB Output is correct
9 Correct 99 ms 10500 KB Output is correct
10 Correct 155 ms 14980 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 146 ms 14504 KB Output is correct
15 Correct 111 ms 11320 KB Output is correct
16 Correct 144 ms 14420 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 171 ms 14936 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 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 87 ms 9628 KB Output is correct
3 Correct 87 ms 9648 KB Output is correct
4 Correct 144 ms 12752 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 87 ms 9628 KB Output is correct
3 Correct 87 ms 9648 KB Output is correct
4 Correct 144 ms 12752 KB Output is correct
5 Correct 146 ms 14348 KB Output is correct
6 Correct 141 ms 14264 KB Output is correct
7 Correct 150 ms 13572 KB Output is correct
8 Correct 141 ms 13116 KB Output is correct
9 Correct 96 ms 9688 KB Output is correct
10 Correct 141 ms 14156 KB Output is correct
11 Correct 154 ms 13100 KB Output is correct
12 Correct 90 ms 9912 KB Output is correct
13 Correct 98 ms 10152 KB Output is correct
14 Correct 94 ms 10196 KB Output is correct
15 Correct 100 ms 10152 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 86 ms 8360 KB Output is correct
18 Correct 94 ms 9900 KB Output is correct
19 Correct 89 ms 9912 KB Output is correct
20 Correct 139 ms 14128 KB Output is correct
21 Correct 140 ms 13164 KB Output is correct
22 Correct 134 ms 13120 KB Output is correct