Submission #581502

#	Time	Username	Problem	Language	Result	Execution time	Memory
581502		kamelfanger83	Rail (IOI14_rail)	C++14	56 / 100	135 ms	872 KiB

rail

#include <iostream>
#include <vector>
#include <limits>
#include "rail.h"
#include <algorithm>
#include <cassert>

using namespace std;

/*int getDistance(int u, int v){
    //cout << u << ", " << v << "?\n";
    //int res; cin >> res; cout << "\n";
    vector<vector<int>> res = {
        {0,12,15,3,2,8,6},
        {12,0,3,11,10,16,14},
        {15,3,0,14,13,19,17},
        {3,11,14,0,1,7,5},
        {2,10,13,1,0,8,6},
        {8,16,19,7,8,0,2},
        {6,14,17,5,6,2,0}
    };
    return res[u][v];
}*/

void findLocation(int n, int first, int location[], int stype[]){
    
    int fl = numeric_limits<int>::max();
    int ifl;
    for(int c = 1; c < n; ++c){
        int d = getDistance(0,c);
        if(d < fl){
            fl = d;
            ifl = c;
        }
    }
    location[ifl] = first + fl;
    stype[ifl] = 2;

    int fr = numeric_limits<int>::max();
    int ifr;
    for(int c = 0; c < n; c++){
        if(c == ifl) continue;
        int d = getDistance(ifl,c);
        if(d < fr){
            fr = d;
            ifr = c;
        }
    }

    location[ifr] = first + fl - fr;
    stype[ifr] = 1;

    vector<vector<int>> ts;

    for(int sol = 0; sol < n; sol++){
        if(sol == ifr || sol == ifl) continue;
        int tu = getDistance(sol,ifl);
        int td = getDistance(sol,ifr);
        ts.push_back({tu, td, sol});
    }

    sort(ts.begin(), ts.end());

    vector<int> leftdowns;
    vector<int> rightups;
    for(vector<int> t : ts){
        int tu = t[0], td = t[1], sol = t[2];
        if(tu + fr == td){
            for(int uc : leftdowns){
                int d = getDistance(sol, uc);
                if(d + (location[ifl] - location[uc]) == tu){
                    location[sol] = location[uc] + d;
                    stype[sol] = 2;
                    goto done;
                }
            }
            location[sol] = location[ifl] - tu;
            stype[sol] = 1;
            leftdowns.push_back(sol);
            done:
            ;
        }
        if(td + fr == tu){
            for(int uc : rightups){
                int d = getDistance(sol, uc);
                if(d + (location[uc] - location[ifr]) == td){
                    location[sol] = location[uc] - d;
                    stype[sol] = 1;
                    goto alsodone;
                }
            }
            location[sol] = location[ifr] + td;
            stype[sol] = 2;
            rightups.push_back(sol);
            alsodone:
            ;
        }
        else{
            //assert(false);
        }
    }
}   

/*int main(){
    int location [7];
    int stype [7];
    findLocation(7, 10, location, stype);
    for(int printr = 0; printr < 7; printr++){
         cout << location[printr] << ", " << stype[printr] << "\n";
    }
    return 0;
}*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:36:14: warning: 'ifl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     location[ifl] = first + fl;
      |              ^~~
rail.cpp:50:14: warning: 'ifr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     location[ifr] = first + fl - fr;
      |              ^~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44