Submission #311600

#	Time	Username	Problem	Language	Result	Execution time	Memory
311600		amunduzbaev	Mechanical Doll (IOI18_doll)	C++14	2 / 100	63 ms	8012 KiB

doll

//#include "grader.cpp"
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> x, y;
int ind=1,in=0;
void solve(int l,int r,vector<int>v,char o){
    if(o=='l'){
        if(l!=r){
            x.push_back(-ind);
            ind++;
        }
        else {
            x.push_back(v[in]);
            in++;
            return;
        }
    }else{
        if(l!=r) {
            y.push_back(-ind);
            ind++;
        }else {
            y.push_back(v[in]);
            in++;
            return;
        }
    }
    int m=(l+r)/2;
    o='l';
    solve(l,m,v,o);
    o='r';
    solve(m+1,r,v,o);
}
void fun(vector<int>v){
    //cout<<ind<<" \n";
    in=0;
    ind++;
    int l=0, r=v.size()-1, m=(l+r)/2;
    solve(l,m,v,'l');
    solve(m+1,r,v,'r');
}

void create_circuit(int M, vector<int> a) {
    n=a.size();
    m=M;
    vector<int>c(m+1,0),ans(m,0),way[m+1];
    way[0].push_back(a[0]);
    c[0]=a[0];

    for(int i=0;i<n-1;i++){
        if(way[a[i]].size()){
            ans[a[i]]=1;
        }
        way[a[i]].push_back(a[i+1]);
        c[a[i]]=a[i+1];
    }

    for(int i=0;i<ans.size();i++){
        if(ans[i]==1){
            c[ans[i]]=-ind;
            fun(way[ans[i]]);
        }
    }
    /*
    for(int i=0;i<c.size();i++)
        cout<<c[i]<<" ";
    cout<<"\n";

    cout<<x.size()<<" "<<y.size()<<" s\n";

    for(int i=0;i<x.size();i++)
        cout<<x[i]<<" "<<y[i]<<" \n";
    */

    answer(c,x,y);

}
/*

9 9
2 9 8 1 3 7 6 4 5


4 4
1 2 1 3

6 6
1 2 1 3 1 4

*/

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

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