Submission #312460

#	Time	Username	Problem	Language	Result	Execution time	Memory
312460		amunduzbaev	Mechanical Doll (IOI18_doll)	C++14	81.15 / 100	219 ms	11800 KiB

doll

//#include "grader.cpp"
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,ind=-1,origin;
vector<vector<int>>way;
vector<int>x,y;
vector<pair<int,int>>t;
bool same(vector<int>v){
    sort(v.begin(),v.end());
    return v[0]==v[v.size()-1] ? 1:0;
}
void solve(vector<int>v , bool c,int i){
    if(c){
        if(same(v)) {x[i]=v[0]; return;}
        else x[i]=ind--;
    }
    else{
        if(same(v)) {y[i]=(v[0]); return;}
        else y[i]=ind--;
    }
    vector<int>l,r;
    for(int j=0;j<v.size();j++){
        if(j%2) r.push_back(v[j]);
        else l.push_back(v[j]);
    }
    x.push_back(0);
    y.push_back(0);
    i=x.size()-1;
    solve(l,1,i);
    solve(r,0,i);
}

void fun(vector<int>v , int a){
    vector<int>l,r;
    int i=0;
    for(;i<a-v.size();i++) {
        l.push_back(origin);
        r.push_back(v[i]);
    }
    int rem=(i%2? 1:0);
    for(;i<v.size();i++){
        if(i%2==rem)l.push_back(v[i]);
        else r.push_back(v[i]);
    }
    x.push_back(0);
    y.push_back(0);
    i=x.size()-1;
    solve(l,1,i);
    solve(r,0,i);
}

int bp(int nx){
    int s=1;
    while(s<nx) s*=2;
    return s;
}
void create_circuit(int M, vector<int> a) {
    n=a.size();
    m=M;
    vector<int>c(m+1,0);
    way.resize(m+1);
    c[0]=a[0];
    for(int i=0;i<n-1;i++){
        way[a[i]].push_back(a[i+1]);
        c[a[i]]=a[i+1];
    }
    way[a[n-1]].push_back(0);
    for(int i=1;i<=m;i++){
        int s=way[i].size();
        if(s<=1) continue;
        c[i]=ind--;
        origin=c[i];
        fun(way[i], bp(s));
    }
    /*
    for(int i=0;i<c.size();i++)
        cout<<c[i]<<" ";
    cout<<"\n";
    for(int i=0;i<x.size();i++)
        cout<<x[i]<<" "<<y[i]<<" \n";
    */

    answer(c,x,y);

}

Compilation message (stderr)

doll.cpp: In function 'void solve(std::vector<int>, bool, int)':
doll.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=0;j<v.size();j++){
      |                 ~^~~~~~~~~
doll.cpp: In function 'void fun(std::vector<int>, int)':
doll.cpp:38:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(;i<a-v.size();i++) {
      |          ~^~~~~~~~~~~
doll.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(;i<v.size();i++){
      |          ~^~~~~~~~~

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