Submission #418567

#	Time	Username	Problem	Language	Result	Execution time	Memory
418567		FlippenFaz	Mechanical Doll (IOI18_doll)	C++11	0 / 100	1 ms	204 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

typedef long long ll;

vector<int> c;
vector<int> x;
vector<int> y;

vector<vector<int>> cons;

void create_circuit(int m, vector<int> a) {

    cons.resize(m+1);
    c.resize(m+1, -1);


    vector<bool> seen;
    vector<bool> seenTwice;
    seen.resize(m, false);
    seenTwice.resize(m, false);
    a.push_back(0);

    c[0] = a[0];

    for (int i = 0; i < a.size(); i++) {
        if (seen[a[i]]) {
            seenTwice[a[i]] = true;
        } else {
            seen[a[i]] = true;
        }
    }

    vector<int> newA;

    bool next = false;
    if (seenTwice[a[0]]) { next = true;}
    for (int i = 1; i < a.size(); i++) {

        if (next) {
            newA.push_back(a[i]);
            next = false;
        } else {
            //cout << " a[i-1] a[i]" << endl;
            //cout << a[i-1] << " " << a[i] << endl;
            c[a[i-1]] = a[i];
        }
        if (seenTwice[a[i]]) {
            next = true;
        }
    }
    
   
    if (newA.size() > 0) {

    int maxPow = ceil(log2(newA.size()));
    newA.resize( pow(2,maxPow), -1 );

    for (int j = 1; j < pow(2,maxPow); j++) {
        x.push_back(-j*2 );
        y.push_back(-j*2 - 1);
    }

    vector<int> ord;
    ord.push_back( pow(2,maxPow) );
    int curPow = pow(2,maxPow-1);
    while (curPow > 0) {
        int curSize = ord.size();
        for (int i = 0; i < curSize; i++) {
            ord.push_back(ord[i] - curPow);
        }
        curPow/=2;
    }

    int cnt = 0;
    for (int j = pow(2,maxPow)-2; j >= pow(2,maxPow-1)-1; j--) {
        y[j] = newA[ord[cnt++]-1];
        x[j] = newA[ord[cnt++]-1];
    }
    }

    answer(c,x,y);

    cout << "SIZE: " <<  x.size() << endl;
    for (int i = 0; i < c.size(); i++) {
        cout << c[i] << endl;
    }
    for (int i = 0; i < x.size(); i++) {
        cout << x[i] << " " << y[i] << endl;
    }  

}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 1; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < c.size(); i++) {
      |                     ~~^~~~~~~~~~
doll.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < x.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56