Submission #100036

#	Time	Username	Problem	Language	Result	Execution time	Memory
100036		errorgorn	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	126 ms	8676 KiB

railroad

#include "railroad.h"
#include <cstring>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
vector<int> gs,gt;
long long memo[16][65539];
int log2(int i){
    int ans=0;
    if (i>=256) ans+=8,i>>=8;
    if (i>=16) ans+=4,i>>=4;
    if (i>=4) ans+=2,i>>=2;
    if (i>=2) ans+=1,i>>=1;
    return ans;
}
int f(int i){
    if (i<0) return 0;
    return i;
}
long long tsp(int i,int bitmask){
    if (bitmask==0) return 0;
    else if (memo[i][bitmask]!=-1) return memo[i][bitmask];
    long long ans=1123456789012345678;
    int c_bitmask=bitmask,temp,log_temp;
    while (c_bitmask!=0){
        temp=c_bitmask&-c_bitmask;
        c_bitmask-=temp;
        log_temp=log2(temp);
        ans=min(ans,tsp(log_temp,bitmask^temp)+ f(gt[i]-gs[log_temp]) );
    }
    return memo[i][bitmask]=ans;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    gs=s,gt=t;
    int n = (int) s.size();
    if (n>16){
        priority_queue<ii> qs,qt;
        for (int x=0;x<n;x++){
            qs.push(ii (s[x],x));
            qt.push(ii (t[x],x));
        }
        ii temp;
        while (qs.size()!=1){
            if (qs.top().second==qt.top().second){
                temp=qs.top(),qs.pop();
            }
            if (qs.top().first>qt.top().second){
                return 1;
            }
            qs.pop(),qt.pop();
            if (temp!=ii(-1,-1)){
                qs.push(temp);
                temp=ii(-1,-1);
            }
        }
        return 0;
    }
    long long ans=1123456789012345678;
    memset(memo,-1,sizeof(memo));
    for (int x=0;x<n;x++){
        ans=min(ans,tsp(x,((1<<n)-1)^(1<<x) ));
    }
    /*for (int x=0;x<n;x++){
        for (int y=0;y<(1<<n);y++){
            printf("%lld ", memo[x][y]);
        }
        printf("\n");
    }*/
    return ans;
}

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