Submission #793112

#	Time	Username	Problem	Language	Result	Execution time	Memory
793112		Ronin13	Rail (IOI14_rail)	C++17	100 / 100	55 ms	4356 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int nmax = 2000000;
int val[nmax];

void findLocation(int N, int first, int location[], int stype[])
{
    int n = N;
    array<int, 2> a[n];
    for(int i = 0; i < n; i++){
        a[i][0] =getDistance(0, i);
        a[i][1] = i;
    }
    sort(a, a + n);
    int l = 0, r = a[1][1];
    stype[r] = 2;
    stype[l] = 1;
    //cout << r;
    location[r] = first + a[1][0];
    location[0] = first;
    val[first + a[1][0]] = 2;
    val[first] = 1;
    for(int i= 2; i < n; i++){
        //
        int ind = a[i][1];
        int d1 = getDistance(l, ind);
        int d2 = getDistance(r, ind);
        //cout << d1 << ' ' << d2 << "\n";
        //cout << location[r] << "\n";
        int p = location[l] + location[r] + d1 - d2;
        p /= 2;
        if(val[p] == 0){
            if(p < first) stype[ind] = 1;
            else stype[ind] = 2; 
        }
      else
        stype[ind] = 3 - val[p];
        if(stype[ind] == 2){
            location[ind] = location[l] + d1;
            val[location[ind]] = stype[ind];
            if(location[ind] > location[r]) r = ind;
        }
        else{
            location[ind] = location[r] - d2;
            val[location[ind]] = stype[ind];
            if(location[ind] < location[l]) l = ind;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:46:7: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   46 |       else
      |       ^~~~
rail.cpp:48:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   48 |         if(stype[ind] == 2){
      |         ^~

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