oj.uz

답안 #96140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96140 2019-02-06T12:26:33 Z bogdan10bos 자동 인형 (IOI18_doll) C++14
6 / 100
 111 ms 11428 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];
    }
    v[lst].push_back(0);

    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:99:13: warning: unused variable 'l' [-Wunused-variable]
   99 |         int l = v[i].size();
      |             ^

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6356 KB Output is correct
3 Correct 27 ms 5196 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 46 ms 7628 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6356 KB Output is correct
3 Correct 27 ms 5196 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 46 ms 7628 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 65 ms 7248 KB Output is correct
9 Correct 93 ms 8560 KB Output is correct
10 Correct 111 ms 11012 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 45 ms 6356 KB Output is correct
3 Correct 27 ms 5196 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 46 ms 7628 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 65 ms 7248 KB Output is correct
9 Correct 93 ms 8560 KB Output is correct
10 Correct 111 ms 11012 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 Runtime error 80 ms 11428 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -