oj.uz

Submission #236247

# Submission time Handle Problem Language Result Execution time Memory
236247 2020-05-31T19:04:00 Z Bilyana Rail (IOI14_rail) C++17
30 / 100
 79 ms 508 KB 
#include <bits/stdc++.h>
//#include "grader.h"
#include "rail.h"

using namespace std;

const int MAXN = 5000 + 100;
const int MAXA = 2e6 + 100;
int dist[MAXN], wh[MAXN];
bool ch[MAXN];
unordered_map<int, int> h;

struct cmp {
    bool operator()(int l, int r) {
        return dist[l] < dist[r];
    }
};

void findLocation(int n, int first, int location[], int stype[])
{
    location[0] = first;
    h[first] = 1;
    stype[0] = 1;
    dist[0] = 0;
    for (int i=1; i<n; i++) {
        dist[i] = getDistance(0, i);
        wh[i] = i;
    }

    sort(wh, wh+n, cmp());
    int l = 0, r = 0;
    location[wh[1]] = first + dist[wh[1]];
    stype[wh[1]] = 2;

    for (int i=2; i<n; i++) {
        h[location[wh[i-1]]] = stype[wh[i-1]];
        if (location[wh[i-1]] < location[l]) {
            l = wh[i-1];
        }
        if (location[wh[i-1]] > location[r]) {
            r = wh[i-1];
        }
        int ld = getDistance(l, wh[i]);
        int rd = getDistance(r, wh[i]);
        //cerr<<wh[i]<<" - "<<l<<' '<<r<<" - "<<location[l]<<' '<<location[r]<<" - "<<ld<<' '<<rd<<endl;

        int temp, temp2;
        temp = location[l] + ld;
        if (temp < location[r]) {
            temp2 = temp - (rd - (location[r] - temp)) / 2;
            if (temp2 >= 0 && h[temp2] == 1) {
                location[wh[i]] = temp;
                stype[wh[i]] = 2;
            }
        }  else {
            temp2 = location[r] - (rd - (temp - location[r])) / 2;
            if (temp2 >= 0 && h[temp2] == 1) {
                location[wh[i]] = temp;
                stype[wh[i]] = 2;
            }
        }

        temp = location[r] - rd;
        if (temp > location[l]) {
            temp2 = temp + (ld - (temp - location[l])) / 2;
            if (temp2 >= 0 && h[temp2] == 2) {
                location[wh[i]] = temp;
                stype[wh[i]] = 1;
            }
        }  else {
            temp2 = location[l] + (ld - (location[l] - temp)) / 2;
            if (temp2 >= 0 && h[temp2] == 2) {
                location[wh[i]] = temp;
                stype[wh[i]] = 1;
            }
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -