Submission #1073677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073677		beaconmc	Rail (IOI14_rail)	C++14	30 / 100	41 ms	604 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;
    
    FOR(i,1,N){
        if (i==one) continue;
        // cout << i << " " << distzero[i] << " " << distone[i] << "FUCK" << endl;
        if (distzero[i] >= distone[i]+minval) lefts.push_back(i);
        else rights.push_back(i);
    }
    // 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());
    deque<ll> curs;
  
    if (lefts.size()){
        ll temp = lefts[0];
        location[temp] = location[one] - distone[temp];
        curs.push_back(lefts[0]);
        stype[temp] = 1;
    
    }
    FOR(i,1,lefts.size()){
        ll temp = lefts[i];
        ll cur = -1;
        bool done = false;
        while (curs.size()){
            cur = curs[0];
            ll dist = getDistance(temp, cur);
            if (dist + distone[cur] == distone[temp]){
                location[temp] = location[cur] + dist;
                stype[temp] = 2;
                done = true;
                break;
            }else{
            	if (dist == distone[cur] + distone[temp]) break;
                curs.pop_front();
            }
        }
        if (!done){
            location[temp] = location[one] - distone[temp];
            stype[temp] = 1;

            curs.push_back(temp);
        }
    }
    curs.clear();
    
    sort(rights.begin(), rights.end(), cmp2);
    if (rights.size()){
        ll temp = rights[0];
        location[temp] = location[0] + distzero[temp];
        curs.push_back(rights[0]);
        stype[temp] = 2;
    }
    FOR(i,1,rights.size()){
        ll temp = rights[i];
        ll cur = -1;
        bool done = false;
        while (curs.size()){
            cur = curs[0];
            ll dist = getDistance(temp, cur);
            if (dist + distzero[cur] == distzero[temp]){
                location[temp] = location[cur] -dist;
                stype[temp] = 1;
                done = true;
                break;
            }else{
            	if (dist == distzero[cur] + distzero[temp]) break;
                curs.pop_front();
            }
        }
        if (!done){
            location[temp] = location[0] + distzero[temp];
            stype[temp] = 2;
            curs.push_back(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++)
......
   85 |     FOR(i,1,lefts.size()){
      |         ~~~~~~~~~~~~~~~~         
rail.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     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++)
......
  118 |     FOR(i,1,rights.size()){
      |         ~~~~~~~~~~~~~~~~~        
rail.cpp:118:5: note: in expansion of macro 'FOR'
  118 |     FOR(i,1,rights.size()){
      |     ^~~

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