oj.uz

Submission #120734

# Submission time Handle Problem Language Result Execution time Memory
120734 2019-06-25T11:09:58 Z onjo0127 Mechanical Doll (IOI18_doll) C++11
12 / 100
 109 ms 9944 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

bool chk[500009], TC[500009];
int N, k, ord[500009], cnt, x[500009], y[500009];
vector<int> A, S, C, X, Y, T;

void go(int idx, int s, int e, int mn, int d) {
    if(s > N) {
        chk[idx] = 1;
        return;
    }
    if(idx >= k) {
        ord[idx] = mn;
        S.push_back(mn);
        return;
    }
    T.push_back(idx); TC[idx] = 1;
    ++cnt;
    int m = s+e >> 1;
    go(idx*2, s, m, mn + (1<<d), d+1);
    go(idx*2+1, m+1, e, mn, d+1);
}

void dfs(int idx, int s, int e) {
    if(s > N) return;
    if(idx*2 >= k) {
        if(ord[idx*2+1] == -1) x[idx] = -1;
        else x[idx] = A[ord[idx*2+1]];
        if(ord[idx*2] == -1) y[idx] = -1;
        else y[idx] = A[ord[idx*2]];
        return;
    }
    int m = s+e >> 1;
    y[idx] = -(idx*2);
    dfs(idx*2, s, m);
    if(!chk[idx*2+1]) {
        x[idx] = -(idx*2+1);
        dfs(idx*2+1, m+1, e);
    }
    else x[idx] = -1;
}

void create_circuit(int M, vector<int> A) {
    A.push_back(0); ::A = A;
    N = ::A.size();
    C.resize(M+1);
    for(int i=0; i<=M; i++) C[i] = -1;
    for(k=1; k<N; k*=2);
    memset(ord, -1, sizeof(ord));
    go(1, 1, k, 1, 0);
    sort(S.begin(), S.end());
    for(int i=1; i<=2*k; i++) if(ord[i] != -1) {
        ord[i] = lower_bound(S.begin(), S.end(), ord[i]) - S.begin();
    }
    X.resize(cnt); Y.resize(cnt);
    dfs(1, 1, k);
    sort(T.begin(), T.end());
    for(int i=0; i<2*k; i++) {
        if(TC[i]) {
            int idx = lower_bound(T.begin(), T.end(), i) - T.begin();
            X[idx] = (x[i] < 0 ? -(lower_bound(T.begin(), T.end(), -x[i]) - T.begin() + 1) : x[i]);
            Y[idx] = (y[i] < 0 ? -(lower_bound(T.begin(), T.end(), -y[i]) - T.begin() + 1) : y[i]);
        }
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void go(int, int, int, int, int)':
doll.cpp:21:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int m = s+e >> 1;
      |             ~^~
doll.cpp: In function 'void dfs(int, int, int)':
doll.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m = s+e >> 1;
      |             ~^~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2272 KB Output is correct
2 Correct 73 ms 7592 KB Output is correct
3 Correct 75 ms 7468 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 13 ms 3404 KB Output is correct
6 Correct 87 ms 9944 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2272 KB Output is correct
2 Correct 73 ms 7592 KB Output is correct
3 Correct 75 ms 7468 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 13 ms 3404 KB Output is correct
6 Correct 87 ms 9944 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Incorrect 109 ms 9804 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2272 KB Output is correct
2 Correct 73 ms 7592 KB Output is correct
3 Correct 75 ms 7468 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 13 ms 3404 KB Output is correct
6 Correct 87 ms 9944 KB Output is correct
7 Correct 3 ms 2252 KB Output is correct
8 Incorrect 109 ms 9804 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Incorrect 88 ms 8864 KB wrong motion
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2252 KB Output is correct
2 Incorrect 88 ms 8864 KB wrong motion
3 Halted 0 ms 0 KB -