Submission #565138

#	Time	Username	Problem	Language	Result	Execution time	Memory
565138		hoanghq2004	Rail (IOI14_rail)	C++14	100 / 100	193 ms	99148 KiB

rail

/* This is sample grader for the contestant */
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#ifndef LOCAL
#include "rail.h"

#endif // LOCAL
#ifdef LOCAL

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;
}
#endif

const int N = 5010;
int d[N][N];

int par[N];

int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

int Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return 0;
    par[v] = u;
    return 1;
}

int vis[N], mind[N];
int lft[N];

void findLocation(int n, int first, int location[], int stype[]) {
    memset(d, -1, sizeof(d));
    auto get = [&](int u, int v) {
        if (u == v) return 0;
        if (u > v) swap(u, v);
        if (d[u][v] == -1) d[u][v] = getDistance(u, v);
        return d[u][v];
    };
    int x = 0, y = 0;
    for (int z = 1; z < n; ++z)
        if (y == 0 || get(x, y) > get(x, z)) y = z;
    location[x] = first, location[y] = location[x] + get(x, y);
    stype[x] = 1, stype[y] = 2;
    vector <pair <int, int>> work;
    for (int z = 0; z < n; ++z) {
        if (z == x || z == y) continue;
        if (get(x, y) > get(z, y) && get(x, z) == get(y, z) + get(x, y)) {
            location[z] = location[y] - get(y, z);
            stype[z] = 1;
        } else work.push_back({get(x, z), z});
    }
    set <pair <int, int>> C, D;
    int rm = x;
    for (int i = 0; i < n; ++i) {
        if (stype[i] == 1) {
            C.insert({location[i], i});
            if (location[i] > location[rm]) rm = i;
        } else if (stype[i] == 2) D.insert({location[i], i});
    }
//    for (int i = 0; i < n; ++i) cout << location[i] << ' ';
//    cout << '\n';
//    cout << location[x] << ' ' << location[y] << '\n';
    sort(work.begin(), work.end());
    for (auto [_, z]: work) {
        if (get(x, z) >= get(x, y) + get(y, z)) { // left
            lft[z] = 1;
            if (C.empty() || C.begin() -> first >= location[x]) {
                stype[z] = 1;
                location[z] = location[y] - get(y, z);
            } else {
                int t = C.begin() -> second;
                for (int s = 0; s < n; ++s) {
                    if (stype[s] != 1) continue;
                    if (get(y, z) + 2 * location[s] == location[y] + location[t] + get(t, z)) {
                        stype[z] = 2;
                        location[z] = get(t, z) + location[t];
                        break;
                    }
                }
                if (stype[z] == 0) {
                    stype[z] = 1;
                    location[z] = location[y] - get(y, z);
                }
            }
        } else { // right
            if (D.empty() || (--D.end()) -> first <= location[y]) {
                stype[z] = 2;
                location[z] = location[x] + get(x, z);
            } else {
                int t = (--D.end()) -> second;
                for (int s = 0; s < n; ++s) {
                    if (stype[s] != 2) continue;
                    if (get(x, z) - 2 * location[s] == - location[x] - location[t] + get(t, z)) {
                        stype[z] = 1;
                        location[z] = location[t] - get(t, z);
                        break;
                    }
                }
                if (stype[z] == 0) {
                    stype[z] = 2;
                    location[z] = location[x] + get(x, z);
                }
            }
        }
        if (stype[z] == 1) C.insert({location[z], z});
        else D.insert({location[z], z});
    }
//    for (int i = 0; i < n; ++i) cout << location[i] << ' ';
//    cout << '\n';
//    cout << x << ' ' << y << '\n';
}
#ifdef LOCAL


void getInput()
{
    freopen("IOI14_rail.inp", "r", stdin);
  int g;
  g = scanf("%d",&SUBTASK);
  g = scanf("%d",&S);
  int s;
  for (s = 0; s < S; s++) {
    int type, location;
    g = scanf(" %d %d",&type,&location);
    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()
{
  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 (int i = 0; i < S; ++i) {
//        if (stations[0].location <= stations[i].location && stations[i].location <= stations[2339].location) {
////        assert(type[i] == stations[i].type);
////        assert(location[i] == stations[i].location);
////            continue;
//        }
////        if (stations[0].location > stations[i].location) {
////            assert(lft[i] == 1 && stations[i].type == type[i]);
////        }
////        \else assert(lft[i] == 0);
////        if (stations[0])
////        assert(type[i] == stations[i].type);
//    }
  for (i = 0; i < S; i++)
    if(type[i]!=stations[i].type || location[i]!=stations[i].location) {
//        cout << i << '\n';
      ok = 0;
    }
//    assert(ok);
  if(ok==0)	printf("Incorrect");
  else	printf("Correct");
  return 0;
}
#endif // LOCAL

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:126:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |     for (auto [_, z]: work) {
      |               ^

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