Submission #563930

#	Time	Username	Problem	Language	Result	Execution time	Memory
563930		qwerasdfzxcl	Rail (IOI14_rail)	C++14	0 / 100	70 ms	636 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int a[5050], b[5050];

inline int myabs(int x){
    if (x<0) return -x;
    return x;
}

void solve(vector<pair<int, int>> &X, int typ, int pos, int n, int location[], int stype[]){
    int mul = typ?1:-1;
    sort(X.begin(), X.end());
    location[X[0].second] = pos + X[0].first * mul;
    stype[X[0].second] = typ;

    int Li = X[0].second, Lx = pos + X[0].first * mul;

    for (int i=1;i<(int)X.size();i++){
        int x = pos + X[i].first * mul;
        if (getDistance(Li, X[i].second)==myabs(Lx-x)){
            location[X[i].second] = Lx - myabs(Lx-x)*mul;
            stype[X[i].second] = typ^1;
        }
        else{
            location[X[i].second] = x;
            stype[X[i].second] = typ;
            Li = X[i].second, Lx = x;
        }
    }
}

void findLocation(int n, int first, int location[], int stype[]){
    //location[0] = first;
    //stype[0] = 1;

    int mn = 1e9, fd = -1;
    for (int i=1;i<n;i++){
        a[i] = getDistance(0, i);
        if (a[i] < mn){
            mn = a[i], fd = i;
        }
    }

    //location[fd] = first + mn;
    //stype[fd] = 2;

    b[0] = a[1];
    vector<pair<int, int>> L = {{mn, 0}}, R = {{0, 1}};
    for (int i=2;i<n;i++){
        b[i] = getDistance(1, i);
        if (a[i]==b[i]+mn) L.emplace_back(b[i], i);
        else R.emplace_back(a[i]-mn, i);
    }

    solve(L, 0, first+mn, n, location, stype);
    solve(R, 1, first+mn, n, location, stype);
    for (int i=0;i<n;i++) stype[i]++;

    //printf("\n");
    //for (int i=0;i<n;i++) printf("%d %d\n", stype[i], location[i]);
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:39:19: warning: variable 'fd' set but not used [-Wunused-but-set-variable]
   39 |     int mn = 1e9, fd = -1;
      |                   ^~

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