Submission #399928

#	Time	Username	Problem	Language	Result	Execution time	Memory
399928		ly20	Rail (IOI14_rail)	C++17	0 / 100	86 ms	412 KiB

rail

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




const int MAXN = 5123;
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[])
{
    location[0] = first;
    stype[0] = 1;
    diste[0] = 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;
    printf("%d\n", 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;
                //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(dt == 0) {
            location[cur] = location[0] + dis;
            lim = cur;
            stype[cur] = 2;
        }
        else {
            location[cur] = location[lim] - dis;
            stype[cur] = 1;
        }
    }
    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;
        if(dt == 0) {
            location[cur] = location[mn] - dis;
            lim = cur;
            stype[cur] = 1;
        }
        else {
            location[cur] = location[lim] + dis;
            stype[cur] = 2;
        }
    }
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0; i < d.size(); i++) {
      |                    ~~^~~~~~~~~~
rail.cpp:54:13: warning: unused variable 'loc' [-Wunused-variable]
   54 |         int loc = location[lim] - dt;
      |             ^~~
rail.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < e.size(); i++) {
      |                    ~~^~~~~~~~~~

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