Submission #399948

#	Time	Username	Problem	Language	Result	Execution time	Memory
399948		ly20	Rail (IOI14_rail)	C++17	100 / 100	100 ms	5052 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;



const int MAXN = 5123;
int id[1123456];
int diste[MAXN], distd[MAXN];
bool cmp(int a, int b) {
    return diste[a] < diste[b];
}
void findLocation(int n, int first, int location[], int stype[])
{
    for(int i = 0; i < 1123456; i++) id[i] = -1;
    location[0] = first;
    stype[0] = 1;
    diste[0] = 0;
    id[first] = 0;
    int mn = -1, ds = 1123456789;
    for(int i = 1; i < n; i++) {
        int d = getDistance(0, i);
        diste[i] = d;
        if(ds > diste[i]) {
            mn = i;
            ds = diste[i];
        }
    }
    stype[mn] = 2;
    location[mn] = location[0] + ds;
    id[location[mn]] = mn;
    //printf("%d\n", mn);
    distd[0] = diste[mn];
    vector <int> d, e;
    for(int i = 1; i < n; i++) {
        if(i == mn) continue;
        distd[i] = getDistance(mn, i);
        if(diste[i] == distd[i] + diste[mn]) {
            if(distd[i] < diste[mn]) {
                location[i] = location[mn] - distd[i];
                stype[i] = 1;
                id[location[i]] = i;
                //printf("%d\n", i);
            }
            else e.push_back(i);
        }
        else d.push_back(i);
    }
    sort(e.begin(), e.end(), cmp);
    sort(d.begin(), d.end(), cmp);
    int lim = mn;
    for(int i = 0; i < d.size(); i++) {
        int cur = d[i];
        int dis;
        if(lim == mn) dis = distd[cur];
        else dis = getDistance(lim, cur);
        int dt = (-diste[cur] + dis + diste[lim]) / 2;
        //dt = - dt;
        int loc = location[lim] - dt;
        if(loc >= 0 && id[loc] != -1 && stype[id[loc]] == 2) {
            location[cur] = location[lim] - dis;
            stype[cur] = 1;
        }
        else {
            location[cur] = location[0] + diste[cur];
            stype[cur] = 2;
            lim = cur;
        }
        id[location[cur]] = cur;
    }
    lim = 0;
    for(int i = 0; i < e.size(); i++) {
        int cur = e[i];
        int dis;
        if(lim == 0) dis = distd[cur];
        else dis = getDistance(lim, cur);
        int dt = (-distd[cur] + dis + distd[lim]) / 2;
        //dt = -dt;
        int loc = location[lim] + dt;
        if(loc >= 0 && id[loc] != -1 && stype[id[loc]] == 1) {
            location[cur] = location[lim] + dis;
            stype[cur] = 2;
        }
        else {
            location[cur] = location[mn] - distd[cur];
            stype[cur] = 1;
            lim = cur;
        }
        id[location[cur]] = cur;
    }
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0; i < d.size(); i++) {
      |                    ~~^~~~~~~~~~
rail.cpp:72:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 0; i < e.size(); i++) {
      |                    ~~^~~~~~~~~~

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