Submission #741653

#	Time	Username	Problem	Language	Result	Execution time	Memory
741653		marvinthang	Rail (IOI14_rail)	C++17	100 / 100	80 ms	588 KiB

rail

/*************************************
*    author: marvinthang             *
*    created: 14.05.2023 18:29:29    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template


void findLocation(int N, int first, int location[], int stype[]) {
	vector <int> dist0(N);
	location[0] = first; stype[0] = 1;
	FOR(i, 1, N) {
		stype[i] = 0;
		dist0[i] = getDistance(0, i);
	}
	vector <int> pos(N - 1);
	vector <int> distp(N);
	iota(ALL(pos), 1);
	sort(ALL(pos), [&] (int a, int b) { return dist0[a] < dist0[b]; });
	int p = pos[0];
	stype[p] = 2;
	location[p] = first + dist0[p];
	vector <int> left, right;
	for (int u: pos) if (u != p) {
		distp[u] = getDistance(p, u);
		if (dist0[u] == dist0[p] + distp[u]) {
			if (distp[u] < dist0[p]) {
				stype[u] = 1;
				location[u] = location[p] - distp[u];
			} else left.push_back(u);
		} else right.push_back(u);
	}
	vector <int> up;
	for (int u: right) {
		if (up.empty()) {
			up.push_back(u);
			stype[u] = 2;
			location[u] = location[0] + dist0[u];
			continue;
		}
		int f = getDistance(up.back(), u);
		int pos = -1;
		for (int u: up) if (location[u] >= location[up.back()] - f) {
			pos = u;
			break;
		}
		assert(pos != -1);
		int t = f - (location[up.back()] - location[pos]);
		if (dist0[u] == dist0[pos] + t) {
			stype[u] = 1;
			location[u] = location[up.back()] - f;
		} else {
			stype[u] = 2;
			location[u] = location[0] + dist0[u];
			up.push_back(u);
		}
	}
	vector <int> down;
	for (int u: left) {
		if (down.empty()) {
			stype[u] = 1;
			location[u] = location[p] - distp[u];
			down.push_back(u);
			continue;
		}
		int f = getDistance(down.back(), u);
		int pos = -1;
		for (int u: down) if (location[u] <= location[down.back()] + f) {
			pos = u;
			break;
		}
		assert(pos != -1);
		int t = f - (location[pos] - location[down.back()]);
		if (distp[u] == distp[pos] + t) {
			stype[u] = 2;
			location[u] = location[down.back()] + f;
		} else {
			stype[u] = 1;
			location[u] = location[p] - distp[u];
			down.push_back(u);
		}
	}
	// REP(i, N) cout << stype[i] << ' ' << location[i] << '\n';
}

#ifdef LOCAL
/* This is sample grader for the contestant */
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "rail.h"

typedef struct Station {
  int index;
  int type;
  int location;
  int L,R;
}STATION;
long long cnt;
static int S,SUBTASK;
static STATION stations[10004];

int cmp_fun_1(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.location < d.location ? -1 : 1;
}

int cmp_fun_2(const void *a,const void *b)
{
	STATION c,d;
	c = *(STATION*)(a);
	d = *(STATION*)(b);
  	return c.index < d.index ? -1 : 1;
}

void now_I_want_to_getLR(){
  int now = stations[S-1].index,i;
  for(i=S-2;i>=0;i--){
    stations[i].R = now;
    if(stations[i].type==2)	now = stations[i].index;
  }
  now = stations[0].index;
  for(i=1;i<S;i++){
    stations[i].L = now;
    if(stations[i].type==1)	now = stations[i].index;
  }
}

int getDistance(int x,int y)
{
  cnt++;
  if(x==y)	return 0;
  if(x<0 || x>=S || y<0 || y>=S)    return -1;
  if(stations[x].location > stations[y].location){
  	int tmp = x;
	x = y;
	y = tmp;
  }
  int ret = 0;
  if(stations[x].type==1 && stations[y].type==1){
    ret = stations[stations[y].R].location-stations[x].location+stations[stations[y].R].location-stations[y].location;
  }else if(stations[x].type==1 && stations[y].type==2){
    ret = stations[y].location-stations[x].location;
  }else if(stations[x].type==2 && stations[y].type==2){
    ret = stations[x].location-stations[stations[x].L].location+stations[y].location-stations[stations[x].L].location;
  }else if(stations[x].type==2 && stations[y].type==1){
    ret = stations[x].location-stations[stations[x].L].location+stations[stations[y].R].location
      -stations[stations[x].L].location+stations[stations[y].R].location-stations[y].location;
  }
  return ret;
}

int seed;
mt19937 rng;
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } 
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } 

void getInput()
{
  int g;
  seed = chrono::steady_clock::now().time_since_epoch().count();
  S = 100;
  rng.seed(seed);
  // cout << seed << '\n';
  SUBTASK = 4;
  // g = scanf("%d",&S);
  int s;
  vector <int> pos(1000);
  iota(ALL(pos), 1);
  for (s = 0; s < S; s++) {
    int type, location, p;
    if (s == 1) {
    	type = 1; location = 0;
    } else if (s == 2) {
    	type = 2; location = 1100;
    } else {
	    p = rand(pos.size());
	    location = pos[p];
	    pos.erase(pos.begin() + p);
	    type = !s ? 1 : rand(1, 2);
	}

    // g = scanf(" %d %d",&type,&location);
    // cout << type << ' ' << location << endl;
    stations[s].index = s;
    stations[s].location = location;
    stations[s].type = type;
    stations[s].L = -1;
    stations[s].R = -1;
  }
  qsort(stations, S, sizeof(STATION), cmp_fun_1);
  now_I_want_to_getLR();
  qsort(stations, S, sizeof(STATION), cmp_fun_2);
}

int serverGetStationNumber()
{
  return S;
}

int serverGetSubtaskNumber()
{
  return SUBTASK;
}

int serverGetFirstStationLocation()
{
  return stations[0].location;
}

int main()
{
	file("rail");
  int i;
  getInput();
  cnt = 0;
  
  int location[10005];
  int type[10005];
  int ok = 1;
  findLocation(S, serverGetFirstStationLocation(),location, type);
  if(SUBTASK==3 && cnt>S*(S-1))	ok = 0;
  if(SUBTASK==4 && cnt>3*(S-1))	ok = 0;
  
  
  for (i = 0; i < S; i++)
    if(type[i]!=stations[i].type || location[i]!=stations[i].location)
      ok = 0;
  if(ok==0)	printf("Incorrect");
  else	printf("Correct");
  return 0;
}
#endif

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