Submission #1043639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043639		deera	Rail (IOI14_rail)	C++14	0 / 100	125 ms	199776 KiB

rail

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

// ██╗░░░░░░█████╗░████████╗███████╗  ██████╗░██╗░░░██╗  ░░███╗░░░█████╗░
// ██║░░░░░██╔══██╗╚══██╔══╝██╔════╝  ██╔══██╗╚██╗░██╔╝  ░████║░░██╔══██╗
// ██║░░░░░███████║░░░██║░░░█████╗░░  ██████╦╝░╚████╔╝░  ██╔██║░░██║░░██║
// ██║░░░░░██╔══██║░░░██║░░░██╔══╝░░  ██╔══██╗░░╚██╔╝░░  ╚═╝██║░░██║░░██║
// ███████╗██║░░██║░░░██║░░░███████╗  ██████╦╝░░░██║░░░  ███████╗╚█████╔╝
// ╚══════╝╚═╝░░╚═╝░░░╚═╝░░░╚══════╝  ╚═════╝░░░░╚═╝░░░  ╚══════╝░╚════╝░

// ███╗░░░███╗██╗███╗░░██╗██╗░░░██╗████████╗███████╗░██████╗  ██╗░░██╗
// ████╗░████║██║████╗░██║██║░░░██║╚══██╔══╝██╔════╝██╔════╝  ╚═╝░██╔╝
// ██╔████╔██║██║██╔██╗██║██║░░░██║░░░██║░░░█████╗░░╚█████╗░  ░░░██╔╝░
// ██║╚██╔╝██║██║██║╚████║██║░░░██║░░░██║░░░██╔══╝░░░╚═══██╗  ░░░╚██╗░
// ██║░╚═╝░██║██║██║░╚███║╚██████╔╝░░░██║░░░███████╗██████╔╝  ██╗░╚██╗
// ╚═╝░░░░░╚═╝╚═╝╚═╝░░╚══╝░╚═════╝░░░░╚═╝░░░╚══════╝╚═════╝░  ╚═╝░░╚═╝
#define all(x) (x).begin(), (x).end()

map<int, int> finished;
bool end_or_eq(int k, int v) {
    return (finished.find(k) == finished.end() || finished[k] == v);
}

void findLocation(int N, int first, int location[], int stype[]) {
    // we already know that
    location[0] = first;
    stype[0] = 1;
    
    vector<vector<int>> dist(N, vector<int>(N, 0));
    dist[0][0] = INT_MAX;


    // x and y are two stations right next to each other
    // with opposite types
    int y = 0;
    int x = 0;
    int min_d = INT_MAX;

    for (int i = 1; i < N; i++) {
        int d = dist[0][i] = dist[i][0] = getDistance(0, i);
        if (d < min_d) {
            x = i;
            d = min_d;
        } 
    }

    stype[x] = 2;
    location[x] = first + min_d;

    vector<int> l, r;

    for(int i = 1; i < N; i++) {
        if (i == x) continue;

        dist[x][i] = getDistance(x, i);
        bool left = (dist[0][x] + dist[x][i] == dist[0][i]);


        if (left && dist[x][i] < dist[0][x]) {
            // simplest case: type 'C' left of X
            stype[i] = 1;
            location[i] = location[x] - dist[x][i];

            // better cadidate for y
            if (location[y] < location[i]) y = i;
        } else if (left) {
            l.push_back(i);
        } else {
            r.push_back(i);
        }
    }

    int c; // corner
    int d = (location[y] - location[0]);
    for(int i: r) dist[y][i] = dist[0][i] - d;

    sort(all(l), [&](int a, int b) {
        return dist[x][a] < dist[x][b];
    });

    sort(all(r), [&](int a, int b) {
        return dist[y][a] < dist[y][b];
    });

    c = l[0];
    location[c] = location[x] - dist[x][c];
    stype[c] = 1;

    finished[location[c]] = stype[c];

    for(auto i: l) {
        if (i == c) continue;

        int d = getDistance(c, i);

        if (end_or_eq(location[c] + (dist[x][c] + d - dist[x][i]) / 2, 2)) {
            location[i] = location[c] + dist[x][c] - dist[x][i];
            stype[i] = 1;
            c = i;
        } else {
            location[i] = location[c] + d;
            stype[i] = 2;
        }

        finished[location[i]] = stype[i];
    }

    c = r[0];
    location[c] = location[y] + dist[y][c];
    stype[c] = 2;

    finished[location[c]] = stype[c];
    for(int i: r) {
        if (i == c) continue;

        int d = getDistance(c, i);
        if (end_or_eq(location[c] - (dist[y][c] + d - dist[y][i]) / 2, 1)) {
            location[i] = location[c] - dist[y][c] + dist[y][i];
            stype[i] = 2;
            c = i;
        } else {
            location[i] = location[c] - d;
            stype[i] = 1;
        }

        finished[location[i]] = stype[i];
    }




    
}

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