oj.uz

Submission #120570

# Submission time Handle Problem Language Result Execution time Memory
120570 2019-06-25T02:29:17 Z onjo0127 Mechanical Doll (IOI18_doll) C++11
0 / 100
 7 ms 4428 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

bool chk[500009];
int N, k, ord[500009], cnt, L[500009], R[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);
    ++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] = -1;
        else X[idx-1] = A[ord[idx*2+1]];
        if(ord[idx*2] == -1) Y[idx-1] = -1;
        else Y[idx-1] = A[ord[idx*2]];
        return;
    }
    int m = s+e >> 1;
    Y[idx-1] = -(idx*2);
    dfs(idx*2, s, m);
    if(!chk[idx*2+1]) {
        X[idx-1] = -(idx*2+1);
        dfs(idx*2+1, m+1, e);
    }
    else X[idx-1] = -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<X.size(); i++) {
        if(X[i] < 0) X[i] = -(lower_bound(T.begin(), T.end(), -X[i]) - T.begin() + 1);
        if(Y[i] < 0) Y[i] = -(lower_bound(T.begin(), T.end(), -Y[i]) - T.begin() + 1);
    }
    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;
      |             ~^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<X.size(); i++) {
      |                  ~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2252 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2252 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2252 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4428 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 4300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 4300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -