oj.uz

Submission #468859

# Submission time Handle Problem Language Result Execution time Memory
468859 2021-08-30T02:44:25 Z vector Mechanical Doll (IOI18_doll) C++17
100 / 100
 194 ms 32596 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define SIZE 100001
using namespace std;

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

vector<int> C, X, Y, psum;
unordered_map<int, int> trash;
vector<int> develop(vector<int> x)
{
    int t=x.size();
    vector<int> y(2*t);
    for (int i=0; i<2*t; i+=2) y[i]=x[i/2];
    for (int i=1; i<2*t; i+=2) y[i]=y[i-1]+t;
    return y;
}
void create_circuit(int M, vector<int> A)
{
    int N=A.size(), cnt=1, x=1;
    C.push_back(A[0]);
    for (int i=1; i<N; i++) A[i-1]=A[i];
    A[N-1]=0;
    for (int i=1; i<=M; i++) C.push_back(-1);
    while ((1<<x)<N) x++;

    vector<int> P, Q;
    int y, t=(1<<x);
    X.push_back(0);
    Y.push_back(0);
    psum.resize(t+1);
    for (int i=0; i<t; i++) trash[-i]=-i;
    for (int i=1; i<=M; i++) trash[i]=i;
    for (int i=1; i<t/2; i++) {
        X.push_back(-2*i);
        Y.push_back(-2*i-1);
    }
    for (int i=t/2; i<t; i++) {
        X.push_back(0);
        Y.push_back(0);
    }
    vector<int> v(1, 1);
    while (v.size()!=t) v=develop(v);
    for (int i=0; i<t-A.size(); i++) {
        y=i/2;
        if (i%2==0) X[t/2+y]=-1;
        else Y[t/2+y]=-1;
        psum[v[i]]=1;
    }
    for (int i=1; i<=t; i++) psum[i]+=psum[i-1];
    for (int i=t-A.size(); i<t; i++) {
        y=i/2;
        if (i%2==0) X[t/2+y]=A[v[i]-psum[v[i]]-1];
        else Y[t/2+y]=A[v[i]-psum[v[i]]-1];
    }
    for (int i=t-1; i>1; i--) if (trash[X[i]]==-1 && trash[Y[i]]==-1) trash[-i]=-1;
    for (int i=2; i<t; i++) if (trash[-i]!=-1) trash[-i]=-(++cnt);
    for (int i=1; i<t; i++) if (trash[-i]!=-1 || i==1) {
        P.push_back(trash[X[i]]);
        Q.push_back(trash[Y[i]]);
    }
    answer(C, P, Q);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:43:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     while (v.size()!=t) v=develop(v);
      |            ~~~~~~~~^~~
doll.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=0; i<t-A.size(); i++) {
      |                   ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 65 ms 12392 KB Output is correct
3 Correct 80 ms 15324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 21 ms 6176 KB Output is correct
6 Correct 106 ms 19256 KB Output is correct
7 Correct 0 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 65 ms 12392 KB Output is correct
3 Correct 80 ms 15324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 21 ms 6176 KB Output is correct
6 Correct 106 ms 19256 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 110 ms 18780 KB Output is correct
9 Correct 151 ms 29256 KB Output is correct
10 Correct 194 ms 32596 KB Output is correct
11 Correct 1 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 65 ms 12392 KB Output is correct
3 Correct 80 ms 15324 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 21 ms 6176 KB Output is correct
6 Correct 106 ms 19256 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 110 ms 18780 KB Output is correct
9 Correct 151 ms 29256 KB Output is correct
10 Correct 194 ms 32596 KB Output is correct
11 Correct 1 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 153 ms 28128 KB Output is correct
15 Correct 125 ms 23168 KB Output is correct
16 Correct 168 ms 27452 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 292 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 167 ms 28852 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 292 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 288 KB Output is correct
5 Correct 0 ms 296 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 296 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 73 ms 14328 KB Output is correct
3 Correct 108 ms 21356 KB Output is correct
4 Correct 147 ms 24800 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 73 ms 14328 KB Output is correct
3 Correct 108 ms 21356 KB Output is correct
4 Correct 147 ms 24800 KB Output is correct
5 Correct 150 ms 27096 KB Output is correct
6 Correct 142 ms 26244 KB Output is correct
7 Correct 140 ms 26556 KB Output is correct
8 Correct 135 ms 25820 KB Output is correct
9 Correct 100 ms 21412 KB Output is correct
10 Correct 132 ms 25604 KB Output is correct
11 Correct 126 ms 25156 KB Output is correct
12 Correct 104 ms 21612 KB Output is correct
13 Correct 82 ms 15264 KB Output is correct
14 Correct 121 ms 22608 KB Output is correct
15 Correct 116 ms 22824 KB Output is correct
16 Correct 4 ms 972 KB Output is correct
17 Correct 78 ms 14672 KB Output is correct
18 Correct 73 ms 14592 KB Output is correct
19 Correct 102 ms 21612 KB Output is correct
20 Correct 134 ms 25408 KB Output is correct
21 Correct 127 ms 25132 KB Output is correct
22 Correct 126 ms 25088 KB Output is correct