Submission #1073585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073585		beaconmc	Rail (IOI14_rail)	C++17	30 / 100	39 ms	624 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;
    ll zero = 0;

    FOR(i,1,N){
        ll dist = getDistance(i,0);
        distzero[i] = dist;
        if (dist < minval){
            minval = dist;
            one = i;
        }
    }
    distone[0] = minval;
    
    location[one] = first+minval;
    stype[one] = 2;
    // cout << "FUCK" << endl;
    // cout << minval << endl;
    // cout << one << " " << location[one] << " " << endl;

    ll fakemini = 1000000000;
    ll fakezero = -1;

    FOR(i,1,N){
        if (i==one) continue;
        distone[i] = getDistance(i,one);
        if (distone[i] < fakemini){
            fakemini = distone[i];
            fakezero = i;
        }
    }

    if (fakemini < minval){
        zero = fakezero;
        FOR(i,0,N){
            if (i==zero) continue;
            
            distzero[i] = getDistance(i, zero);
        }
        location[zero] = location[one] - fakemini;
        stype[zero] = 1;
    }


    vector<ll> lefts, rights;

    FOR(i,0,N){
        if (i==one) continue;
        if (i==zero) continue;
        // cout << i << " " << distzero[i] << " " << distone[i] << "FUCK" << endl;
        if (distzero[i] > distone[i]) lefts.push_back(i);
        else rights.push_back(i);
    }
    // cout << "LMAO" << rights.size() << endl;
    // for (auto&i : rights) cout << i << " ";
    // cout << 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 = -1;
    if (lefts.size()){
        ll temp = lefts[0];
        location[temp] = location[one] - distone[temp];
        cur = lefts[0];
        stype[temp] = 1;

    }
    FOR(i,1,lefts.size()){
        ll temp = lefts[i];
        ll dist = getDistance(temp, cur);
        // cout << "FUCK" << dist << " " << distone[cur] << " " << distone[temp] << endl;
        if (dist + distone[cur] == distone[temp]){
            location[temp] = location[cur] + dist;
            stype[temp] = 2;
        }else{
            location[temp] = location[one] - distone[temp];
            stype[temp] = 1;
            cur = temp;
        }
    }

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

    
    // FOR(i,0,N){
    //     cout << location[i] << " ";
    // }
    // cout << endl;




}

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++)
......
  104 |     FOR(i,1,lefts.size()){
      |         ~~~~~~~~~~~~~~~~         
rail.cpp:104:5: note: in expansion of macro 'FOR'
  104 |     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++)
......
  125 |     FOR(i,1,rights.size()){
      |         ~~~~~~~~~~~~~~~~~        
rail.cpp:125:5: note: in expansion of macro 'FOR'
  125 |     FOR(i,1,rights.size()){
      |     ^~~

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