Submission #187212

#	Time	Username	Problem	Language	Result	Execution time	Memory
187212		PedroBigMan	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	2082 ms	59652 KiB

railroad

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include "railroad.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF 100000000000000000LL
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
void Expose(set<pl> x) 
{
    set<pl>::iterator it=x.begin();
    REP(i,0,x.size()) {cout<<(*it).ff<<" "<<(*it).ss<<endl; it++;}
}

ll Check(set<pl> a, set<pl> b)
{
    ll N=a.size();
    vector<ll> p; REP(i,0,N) {p.pb(-1);}
    set<pl>::iterator it1,it2;
    it1=a.begin(); ll ind=0;
    while(it1!=a.end())
    {
        pl val1=*it1;  
        it2=lower_bound(b.begin(),b.end(),mp(val1.ff+1,-INF));
        if(it2==b.begin()) {it1++; continue;}
        it2--;
        if((*it2).ss==val1.ss) 
        {
            if(it2==b.begin()) {it1++; continue;}
            it2--;
            p[ind]=1LL;
            b.erase(it2);
        }
        it1++; ind++;
    }
    ll suma=0LL; ll sumb=0LL;
    it1=a.begin();
    REP(i,0,N)
    {
        if(p[i]!=-1) {it1++;continue;}
        suma+=(*it1).ff;
        it1++;
    }
    it2=b.begin();
    REP(i,0,b.size()) {sumb+=(*it2).ff; it2++;}
    return sumb-suma;
}

ll plan_roller_coaster(vector<int> sss, vector<int> ttt) 
{
    ll N=sss.size();
    set<pl> s,t;
    REP(i,0,N)
    {
        s.insert(mp((ll) sss[i],i));
        t.insert(mp((ll) ttt[i],i));
    }
    set<pl>:: iterator it1,it2;
    it1=s.begin(); it2=t.end(); it2--;
    ll ans=INF;
    REP(rems,0,2)
    {
        REP(remt,0,2)
        {
            it1=s.begin(); it2=t.end(); REP(j,0,rems) {it1++;} REP(j,0,remt) {it2--;} it2--;
            pl rv1=*it1;
            pl rv2=*it2;
            if(rv1.ss!=rv2.ss)
            {
                s.erase(it1); t.erase(it2);
                ans=min(ans,Check(s,t)); 
                t.insert(rv2); s.insert(rv1);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'void Out(std::vector<long long int>)':
railroad.cpp:15:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
railroad.cpp:24:29:
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                             ~~~~~~~~~~~~
railroad.cpp:24:25: note: in expansion of macro 'REP'
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                         ^~~
railroad.cpp: In function 'void Expose(std::set<std::pair<long long int, long long int> >)':
railroad.cpp:15:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
railroad.cpp:28:9:
     REP(i,0,x.size()) {cout<<(*it).ff<<" "<<(*it).ss<<endl; it++;}
         ~~~~~~~~~~~~             
railroad.cpp:28:5: note: in expansion of macro 'REP'
     REP(i,0,x.size()) {cout<<(*it).ff<<" "<<(*it).ss<<endl; it++;}
     ^~~
railroad.cpp: In function 'll Check(std::set<std::pair<long long int, long long int> >, std::set<std::pair<long long int, long long int> >)':
railroad.cpp:15:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
railroad.cpp:61:9:
     REP(i,0,b.size()) {sumb+=(*it2).ff; it2++;}
         ~~~~~~~~~~~~             
railroad.cpp:61:5: note: in expansion of macro 'REP'
     REP(i,0,b.size()) {sumb+=(*it2).ff; it2++;}
     ^~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36