Submission #415006

#	Time	Username	Problem	Language	Result	Execution time	Memory
415006		MeGustaElArroz23	Roller Coaster Railroad (IOI16_railroad)	C++14	Compilation error	0 ms	0 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;

const ll INF=1000000000000000000;

ll potencia(ll a, ll n){
    if (n==0) return 1;
    ll sol=potencia(a,n/2);
    sol*=sol;
    if (n%2) sol*=a;
    return sol;
}

ll vb_to_int(vb x){
    ll pot=1;
    ll sol=0;
    for (int i=0;i<x.size();i++){
        sol+=pot*x[i];
        pot*=2;
    }
    return sol;
}

int n;
vii in_out;
vvi sol; //le metemos uno mas

ll recurs(vb mask, int ac){
    //cerr << ac;
    mask[ac]=false;
    if (sol[vb_to_int(mask)][ac]) return sol[vb_to_int(mask)][ac]-1;
    for (int i=0;i<n;i++){
        if (mask[i]) break;
        if (i==n-1) return 0;
    }
    ll mejor=INF;
    for (int i=0;i<n;i++){
        if (mask[i]) mejor=min(mejor,recurs(mask, i)+max(ll(0),in_out[ac].second-in_out[i].first));
    }
    sol[vb_to_int(mask)][ac]=mejor+1;
    return mejor;
}

//4 1 7 4 3 5 8 6 6

ll plan_roller_coaster(vi in, vi out) {
    //if (false){ //subtask 3
    //    int n=in.size();
    //    multiset<pii> pares;
    //    for (int i=0;i<n;i++) pares.insert(pii{in[i],out[i]});
    //    int ac=1;
    //    for (int i=0;i<n;i++){
    //        //cerr << ac << ' ';
    //        cerr << ac << ' ';
    //        auto x=pares.upper_bound(pii{ac,0});
    //        pii y=*x;
    //        if (x==pares.end()) return 1;
    //        if (i<n-1 and pares.upper_bound(pii{y.second,0})==pares.end()) x++;
    //        if (x==pares.end()) return 1;
    //        ac=(*x).second;
    //        pares.erase(x);
    //    }
    //    return 0;
    //}
    n=in.size();
    //cerr<<"HOLA";
    in_out=vii(n);
    sol=vvi(potencia(2,n),vi(n,0));
    for (ll i=0;i<n;i++){ in_out[i]=pii{in[i],out[i]};}
    //cerr<<"HOLA";
    ll mejor=INF;
    for (ll i=0;i<n;i++) mejor=min(mejor,recurs(vb(n,true),i));
    return mejor;
}

Compilation message (stderr)

railroad.cpp: In function 'll vb_to_int(vb)':
railroad.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=0;i<x.size();i++){
      |                  ~^~~~~~~~~
/usr/bin/ld: /tmp/ccc7yPwm.o: in function `main':
grader.cpp:(.text.startup+0xf4): undefined reference to `plan_roller_coaster(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status