Submission #741653

# Submission time Handle Problem Language Result Execution time Memory
741653 2023-05-14T13:57:10 Z marvinthang Rail (IOI14_rail) C++17
100 / 100
80 ms 588 KB
/*************************************
*    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
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 388 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 388 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 70 ms 516 KB Output is correct
2 Correct 67 ms 516 KB Output is correct
3 Correct 67 ms 520 KB Output is correct
4 Correct 67 ms 588 KB Output is correct
5 Correct 75 ms 496 KB Output is correct
6 Correct 69 ms 500 KB Output is correct
7 Correct 79 ms 500 KB Output is correct
8 Correct 68 ms 512 KB Output is correct
9 Correct 66 ms 500 KB Output is correct
10 Correct 68 ms 516 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 70 ms 572 KB Output is correct
2 Correct 67 ms 512 KB Output is correct
3 Correct 72 ms 504 KB Output is correct
4 Correct 67 ms 516 KB Output is correct
5 Correct 69 ms 500 KB Output is correct
6 Correct 75 ms 492 KB Output is correct
7 Correct 77 ms 512 KB Output is correct
8 Correct 72 ms 496 KB Output is correct
9 Correct 70 ms 500 KB Output is correct
10 Correct 67 ms 504 KB Output is correct
11 Correct 72 ms 500 KB Output is correct
12 Correct 68 ms 508 KB Output is correct
13 Correct 68 ms 496 KB Output is correct
14 Correct 80 ms 500 KB Output is correct
15 Correct 69 ms 512 KB Output is correct
16 Correct 68 ms 508 KB Output is correct
17 Correct 74 ms 500 KB Output is correct
18 Correct 73 ms 500 KB Output is correct
19 Correct 70 ms 512 KB Output is correct
20 Correct 73 ms 588 KB Output is correct