Submission #302161

#	Time	Username	Problem	Language	Result	Execution time	Memory
302161		peti1234	Rail (IOI14_rail)	C++17	100 / 100	99 ms	760 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
const int c=5002;
int a[c], b[c], pos=1, js, bs, el, id, x, kt;
vector<int> regi;
vector<pair<int, int> > bal, jobb;
int tav(int a, int b) {return getDistance(a, b);}
void findLocation(int n, int first, int l[], int s[]) {
    for (int i=1; i<n; i++) {
        a[i]=tav(0, i);
        if (a[i]<a[pos]) pos=i;
    }
    l[0]=first, l[pos]=l[0]+a[pos], s[0]=1, s[pos]=2, kt=a[pos];
    for (int i=1; i<n; i++) if (i!=pos) {
        b[i]=tav(pos, i);
        kt=min(kt, b[i]);
    }
    for (int i=1; i<n; i++) if (i!=pos) {
        if (a[i]+2*kt==b[i]+a[pos]) jobb.push_back({a[i], i});
        else bal.push_back({b[i], i});
    }
    sort(jobb.begin(), jobb.end()), sort(bal.begin(), bal.end());
    js=jobb.size(), bs=bal.size();
    if (js) {
        id=jobb[0].second, el=id;
        s[id]=2, l[id]=l[0]+a[id];
        regi.push_back(id);
        for (int i=1; i<js; i++) {
            id=jobb[i].second, x=tav(el, id);
            bool jo=0;
            for (int i=0; i<regi.size(); i++) if (a[el]+x-2*(l[el]-l[regi[i]])==a[id]) jo=1;
            if (jo) s[id]=1, l[id]=l[el]-x;
            else s[id]=2, l[id]=l[0]+a[id], el=id, regi.push_back(id);
        }
    }
    regi.clear();
    if (bs) {
        id=bal[0].second, el=id;
        s[id]=1, l[id]=l[pos]-b[id];
        regi.push_back(id);
        for (int i=1; i<bs; i++) {
            id=bal[i].second, x=tav(el, id);
            bool jo=0;
            for (int i=0; i<regi.size(); i++) if (b[el]+x-2*(l[regi[i]]-l[el])==b[id]) jo=1;
            if (jo) s[id]=2, l[id]=l[el]+x;
            else s[id]=1, l[id]=l[pos]-b[id], el=id, regi.push_back(id);
        }
    }
    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for (int i=0; i<regi.size(); i++) if (a[el]+x-2*(l[el]-l[regi[i]])==a[id]) jo=1;
      |                           ~^~~~~~~~~~~~
rail.cpp:45:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for (int i=0; i<regi.size(); i++) if (b[el]+x-2*(l[regi[i]]-l[el])==b[id]) jo=1;
      |                           ~^~~~~~~~~~~~

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