oj.uz

Submission #96139

# Submission time Handle Problem Language Result Execution time Memory
96139 2019-02-06T12:24:08 Z bogdan10bos Mechanical Doll (IOI18_doll) C++14
2 / 100
 65 ms 7708 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

int S;
vector<int> X, Y;

int make_switch(vector<int> left, vector<int> right)
{
    if(left.size() != right.size()) return -(1 << 30);
    if(left.size() == 1)
    {
        S++;
        X.push_back(left[0]);
        Y.push_back(right[0]);
        return -S;
    }

    S++;
    int id = S;
    X.push_back(0);
    Y.push_back(0);

    int l;
    vector<int> lft, rgt;

    l = left.size();
    lft.clear(); rgt.clear();
    for(int i = 0; i < l / 2; i++)
        lft.push_back(left[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(left[i]);
    int sl = make_switch(lft, rgt);

    l = right.size();
    lft.clear(); rgt.clear();
    for(int i = 0; i < l / 2; i++)
        lft.push_back(right[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(right[i]);
    int sr = make_switch(lft, rgt);

    X[id - 1] = sl;
    Y[id - 1] = sr;
    return -id;
}

int make_switch(vector<int> v)
{
    if(v.empty())   return 0;
    if(v.size() == 1)
        return v[0];

    int l = v.size();
    assert( (l & (l - 1)) == 0 );

    vector<int> newv;
    newv.resize(v.size());
    int lg = 0;
    for(lg = 0; (1 << lg) < v.size(); lg++);
    for(int i = 0; i < v.size(); i++)
    {
        int msk = i;
        int rmsk = 0;
        for(int j = 0; j < lg; j++)
            if((msk >> j) & 1)
                rmsk |= (1 << (lg - j - 1));
        newv[rmsk] = v[i];
    }

    vector<int> lft, rgt;
    for(int i = 0; i < l / 2; i++)
        lft.push_back(newv[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(newv[i]);
    return make_switch(lft, rgt);
}

void create_circuit(int M, vector<int> A)
{
    vector< vector<int> > v;
    v.resize(M + 2);
    int lst = 0;
    for(int i = 0; i < A.size(); i++)
    {
        v[lst].push_back(A[i]);
        lst = A[i];
    }

    vector<int> ex;
    ex.resize(M + 1);
    X.clear(), Y.clear();

    S = 0;
    for(int i = 0; i <= M; i++)
    {
        int l = v[i].size();
        ex[i] = make_switch(v[i]);
    }

    answer(ex, X, Y);
}

Compilation message

doll.cpp: In function 'int make_switch(std::vector<int>)':
doll.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(lg = 0; (1 << lg) < v.size(); lg++);
      |                 ~~~~~~~~~~^~~~~~~~~~
doll.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
doll.cpp:98:13: warning: unused variable 'l' [-Wunused-variable]
   98 |         int l = v[i].size();
      |             ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 42 ms 6380 KB Output is correct
3 Correct 35 ms 5152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 58 ms 7708 KB Output is correct
7 Correct 2 ms 204 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 42 ms 6380 KB Output is correct
3 Correct 35 ms 5152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 58 ms 7708 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Incorrect 65 ms 7204 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 42 ms 6380 KB Output is correct
3 Correct 35 ms 5152 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 58 ms 7708 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Incorrect 65 ms 7204 KB wrong motion
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 332 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 Incorrect 1 ms 204 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

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