Submission #503589

#	Time	Username	Problem	Language	Result	Execution time	Memory
503589		doowey	철로 (IOI14_rail)	C++14	30 / 100	185 ms	580 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 d0, d1;
    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);
            // check whether pos is a valid one
            pos = lef + askl;
            valid = true;
            // get distance between right and pos
            dist = (int)1e9;
            for(int j = 0 ; j < n; j ++ ){
                if(calc[j]){
                    if(stype[j] == 0 && location[j] < pos && location[j] < rig){
                        dist = min(dist, rig - location[j] + pos - location[j]);
                    }
                }
            }
            if(dist != askr) valid = false;
            // get distance between 0 and pos
            dist = (int)1e9;
            if(pos > location[0]){
                dist = pos - location[0];
            }
            else{
                d0 = d1 = (int)1e9;
                for(int j = 0 ; j < n; j ++ ){
                    if(calc[i]){
                        if(stype[j] == 1 && location[j] > location[0]){
                            d0 = min(d0, location[j] - location[0]);
                        }
                        if(stype[j] == 0 && location[j] < pos){
                            d1 = min(d1, pos - location[j]);
                        }
                    }
                }
                dist = d0 + d1;
            }
            if(dist != d[id]) valid = false;
            if(valid){
                location[id] = pos;
                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:35: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]
   35 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~

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