Submission #1076677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076677		beaconmc	Rail (IOI14_rail)	C++14	30 / 100	52 ms	616 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
    
typedef long long ll;
    
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
    
using namespace std;
    
const ll maxn = 5005;
    
ll distzero[5005];
    
ll distone[5005];
    
bool cmp(ll a, ll b){
    return distone[a]<distone[b];
}
    
bool cmp2(ll a, ll b){
    return distzero[a]<distzero[b];
}
    
void findLocation(int N, int first, int location[], int stype[])
{
    ll minval = 1000000000000;
    ll one = -1;
    location[0] = first;
    stype[0] = 1;
    
    FOR(i,1,N){
        ll dist = getDistance(i,0);
        distzero[i] = dist;
        if (dist < minval){
            minval = dist;
            one = i;
        }
    }
    
    location[one] = first+minval;
    stype[one] = 2;
    // cout << "FUCK" << endl;
    // cout << minval << endl;
    // cout << one << " " << location[one] << " " << endl;
    
    ll fakemini = 1000000000;
    
    FOR(i,1,N){
        if (i==one) continue;
        distone[i] = getDistance(i,one);
        fakemini = min(fakemini, distone[i]);
    }
 
    
    vector<ll> lefts, rights;
    vector<ll> left2, right2;

    
    FOR(i,1,N){
        if (i==one) continue;
        // cout << i << " " << distzero[i] << " " << distone[i] << "FUCK" << endl;
        if (distzero[i] >= distone[i]) lefts.push_back(i);
        else rights.push_back(i);
    }

    left2 = lefts;
    right2 = rights;
    // cout << "LMAO" << rights.size() << endl;


    sort(lefts.begin(), lefts.end(), cmp);
    
    reverse(lefts.begin(), lefts.end());
    while (lefts.size() && distone[lefts[lefts.size()-1]] < minval){
        ll temp = lefts[lefts.size()-1];


        location[temp] = location[one] - distone[temp];
        stype[temp] = 1;
        lefts.pop_back();
    }
    
    reverse(lefts.begin(), lefts.end());
    ll cur;
    vector<ll> stuff;

    if (lefts.size()){
        ll temp = lefts[0];
        location[temp] = location[one] - distone[temp];
        cur = temp;
        stype[temp] = 1;
        stuff.push_back(-location[temp]);

    }

    
    ll cnt = 0;


    FOR(i,1,lefts.size()){
        ll temp = lefts[i];

        ll dist = getDistance(cur, temp);
        ll potential = location[cur] + dist;

        ll sus = -(*upper_bound(stuff.begin(), stuff.end(), -potential));
        //cout << abs(sus -potential) << " "<< location[one] << " " << sus << " " << distone[temp] << endl;

        if ((abs(sus -potential) + location[one] - sus) == distone[temp]){
            location[temp] = potential;
            stype[temp] = 2;
        }
        else{
            location[temp] = location[one] - distone[temp];
            stype[temp] = 1;
            cur = temp;
            stuff.push_back(-location[temp]);
        }
    }
    stuff.clear();

    
    sort(rights.begin(), rights.end(), cmp2);
    if (rights.size()){
        ll temp = rights[0];
        location[temp] = location[0] + distzero[temp];
        cur = rights[0];
        stype[temp] = 2;
        stuff.push_back(location[temp]);
    }
    FOR(i,1,rights.size()){
        ll temp = rights[i];
        ll dist = getDistance(cur, temp);
        ll potential = location[cur] - dist;

        ll sus = *upper_bound(stuff.begin(), stuff.end(), potential);

        if (abs(sus - potential) + sus - location[0] == distzero[temp]){
		    location[temp] = location[cur] -dist;
		    stype[temp] = 1;
        }

        else{
            location[temp] = location[0] + distzero[temp];
            stype[temp] = 2;
            cur = temp;
            stuff.push_back(location[temp]);
        }
    }

    
    
    
    
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  101 |     FOR(i,1,lefts.size()){
      |         ~~~~~~~~~~~~~~~~         
rail.cpp:101:5: note: in expansion of macro 'FOR'
  101 |     FOR(i,1,lefts.size()){
      |     ^~~
rail.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  132 |     FOR(i,1,rights.size()){
      |         ~~~~~~~~~~~~~~~~~        
rail.cpp:132:5: note: in expansion of macro 'FOR'
  132 |     FOR(i,1,rights.size()){
      |     ^~~
rail.cpp:98:8: warning: unused variable 'cnt' [-Wunused-variable]
   98 |     ll cnt = 0;
      |        ^~~
rail.cpp:104:30: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |         ll dist = getDistance(cur, temp);
      |                   ~~~~~~~~~~~^~~~~~~~~~~

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