Submission #503661

#	Time	Username	Problem	Language	Result	Execution time	Memory
503661		doowey	Rail (IOI14_rail)	C++14	100 / 100	289 ms	628 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

using namespace std;

typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 5010;
int d[N];
bool calc[N];

void findLocation(int n, int first, int location[], int stype[]){
    vector<pii> ord;
    for(int i = 1; i < n; i ++ ){
        d[i] = getDistance(0, i);
        ord.push_back(mp(d[i], i));
    }
    sort(ord.begin(), ord.end());
    location[0] = first;
    stype[0] = 0;
    calc[0]=true;
    int ii = 0;
    int jj;
    int lef, rig;
    int askl, askr;
    int id;
    int pos;
    int dist;
    bool valid;
    int en, st;
    int check;
    int pick;
    for(int i = 0 ; i < ord.size(); i ++ ){
        if(i == 0){
            location[ord[i].se] = first + ord[i].fi;
            stype[ord[i].se] = 1;
            calc[ord[i].se] = true;
            lef = first;
            rig = location[ord[i].se];
            jj = ord[i].se;
        }
        else{
            id = ord[i].se;
            askl = getDistance(ii, id);
            askr = getDistance(jj, id);

            pos = lef + askl;
            pick = -1;

            for(int j = 0 ; j < n; j ++ ){
                if(!calc[j]) continue;
                if(location[j] <= min(pos, rig) && stype[j] == 0){
                    check = (rig - location[j]) + (pos - location[j]);
                    if(check == askr){
                        pick = 0;
                    }
                }
            }
            pos = rig - askr;
            for(int j = 0 ; j < n; j ++ ){
                if(!calc[j]) continue;
                if(location[j] >= max(pos, lef) && stype[j] == 1){
                    check = (location[j] - lef) + (location[j] - pos);
                    if(check == askl){
                        pick = 1;
                    }
                }
            }
            if(pick == -1){
                pos = lef + askl;
                if(d[id] == pos - location[0]){
                    pick = 0;
                }
                else{
                    pick = 1;
                }
            }
            if(pick == 0){
                location[id] = lef + askl;
                stype[id] = 1;
                if(location[id] > rig){
                    rig = location[id];
                    jj = id;
                }
            }
            else{
                location[id] = rig - askr;
                stype[id] = 0;
                if(location[id] < lef){
                    lef = location[id];
                    ii = id;
                }
            }
            calc[id] = true;

        }
    }
    for(int i = 0 ; i < n; i ++ ){
        stype[i] ++ ;
    }

}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
rail.cpp:32:9: warning: unused variable 'dist' [-Wunused-variable]
   32 |     int dist;
      |         ^~~~
rail.cpp:33:10: warning: unused variable 'valid' [-Wunused-variable]
   33 |     bool valid;
      |          ^~~~~
rail.cpp:34:9: warning: unused variable 'en' [-Wunused-variable]
   34 |     int en, st;
      |         ^~
rail.cpp:34:13: warning: unused variable 'st' [-Wunused-variable]
   34 |     int en, st;
      |             ^~

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