Submission #49384

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
49384	2018-05-28 07:07:43	imeimi2000	Rail (IOI14_rail)	C++17	100 / 100	143 ms	916 KiB

rail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "rail.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 5000;
int n;
int d0[MAXN];
int d1[MAXN];
int rd[MAXN];
int *l, *t;
void calc(vector<int> &ps, int s) {
    sort(ps.begin(), ps.end(), [&](int i, int j) { return rd[i] < rd[j]; });
    set<int> mp;
    l[ps[0]] = l[s] + rd[ps[0]];
    t[ps[0]] = 2;
    int mx = ps[0];
    mp.insert(l[mx] << 1);
    for (int i = 1; i < ps.size(); ++i) {
        int fn = (l[mx] << 1) + rd[ps[i]] - rd[mx] - getDistance(ps[i], mx);
        if (mp.find(fn) != mp.end()) {
            l[ps[i]] = fn - rd[ps[i]] - l[s];
            t[ps[i]] = 1;
        }
        else {
            l[ps[i]] = l[s] + rd[ps[i]];
            t[ps[i]] = 2;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

rail.cpp: In function 'void calc(std::vector<int>&, int)':
rail.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < ps.size(); ++i) {
                     ~~^~~~~~~~~~~

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