제출 #587499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587499		LastRonin	철로 (IOI14_rail)	C++14	0 / 100	67 ms	640 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
using namespace std;
/*
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;
}
 
 
void getInput()
{
  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;
}
/**/
 
const int N = 5e3 + 100;
 
int cont = 0;
bool le[N];
int dist[N][N];
bool was[N][N];
 
int get(int a, int b) {
	if(was[a][b])return dist[a][b];
	cont++;
	was[a][b] = 1;
	dist[a][b] = getDistance(a, b);
	return dist[a][b];
}
 
void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first;
	stype[0] = 1;
	vector<pair<int, int>> z;
	for(int i = 1; i < n; i++) {
		dist[0][i] = get(0, i);
		was[0][i] = 1;
		z.pb(mp(dist[0][i], i));		
	}
	sort(z.begin(), z.end());
	ll L = first, Lid = 0;
	ll R = first + z[0].f, Rid = z[0].s;
	location[Rid] = R;
	stype[Rid] = R;
	vector<int> C, D;
	C.pb(Lid);
	D.pb(Rid);	
	for(int j = 1; j < n - 1; j++) {
		if(Lid == 0) {       
			ll a = z[j].f;
			ll b = get(Rid, z[j].s);
			ll pos = R - b;
			// we have two hypothetical positions
			// R - b or L + a
			ll pos1 = R - b;// type C
			ll pos2 = L + a;// type D
			// check with 1 query
			ll ind = -1, bliz = 1e9;
			for(int j = 0; j < D.size(); j++) {
				if(location[D[j]] > pos1) {
					if(bliz > location[D[j]]) {
						bliz = location[D[j]];
						ind = j;
					}
				}
			}
			if(ind == Rid) {
				if((R - L) + b == a) {
					location[z[j].s] = pos1;
					stype[z[j].s] = 1;
					C.pb(z[j].s);
					if(pos1 < L)
						L = pos1, Lid = z[j].s;
				} else {
					location[z[j].s] = pos2;
					stype[z[j].s] = 2;
					D.pb(z[j].s);
					if(pos2 > R)
						R = pos2, Rid = z[j].s;
				}       
			}
			else {
				assert(ind != -1);
				ll di = get(ind, z[j].s);
				if(di + dist[0][ind] == dist[0][z[j].s]) {
					location[z[j].s] = pos1;
					stype[z[j].s] = 1;
					C.pb(z[j].s);
					if(pos1 < L)
						L = pos1, Lid = z[j].s;
				} else {
					location[z[j].s] = pos2;
					stype[z[j].s] = 2;
					D.pb(z[j].s);
					if(pos2 > R)
						R = pos2, Rid = z[j].s;
				}       
			}
		} else {
			ll d1 = get(Lid, z[j].s);
			if(d1 < location[0] - location[Lid]) {
				ll pos1 = location[Lid] + d1;
				ll bliz = -1e9, ind = -1;
				for(int j = 0; j < C.size(); j++) {
					if(pos1 > location[C[j]] && bliz < location[C[j]]) {
						bliz = location[C[j]];
						ind = C[j];																			
				   	}
			   	}
			   	if(ind == Lid) {
			   		if(d1 + dist[0][Lid] == dist[0][z[j].s]) {	
						location[z[j].s] = pos1;
						stype[z[j].s] = 2;
						D.pb(z[j].s);
			   		} else {
						location[z[j].s] = location[z[0].s] - dist[0][z[j].s] + dist[0][z[0].s];
						stype[z[j].s] = 1;
						C.pb(z[j].s);
						if(location[z[j].s] < L)
							L = location[z[j].s], Lid = z[j].s;
			   		}
			   	} else {
			   		ll d2 = get(ind, z[j].s);
			   		if(d2 + dist[0][ind] == dist[0][z[j].s]) {
			   			location[z[j].s] = pos1;
			   			stype[z[j].s] = 2;
			   			D.pb(z[j].s);
			   		} else {
						location[z[j].s] = location[z[0].s] - dist[0][z[j].s] + dist[0][z[0].s];
						stype[z[j].s] = 1;
						C.pb(z[j].s);
						if(location[z[j].s] < L)
							L = location[z[j].s], Lid = z[j].s;
			   		}
			   	}
			} else {
				// d1 = get(Lid, z[j].s);
				if((location[0] - L) + dist[0][z[j].s] == d1) {
					ll d2 = get(Rid, z[j].s);
					if(d2 > R - L) {
						// green or blue
						ll posgre = R - d2;
						ll posblu = location[0] + dist[0][z[j].s];
						if(location[z[0].s] - posgre + dist[0][z[0].s] != dist[0][z[j].s]) {
							location[z[j].s] = posblu;
							stype[z[j].s] = 2;
							D.pb(z[j].s);	
						}
					} else {
						// yellow or blue 
					}
					// but z[0].					
				} else {
					location[z[j].s] = R - get(Rid, z[j].s);
					stype[z[j].s] = 1;
					C.pb(z[j].s);
					if(location[z[j].s] < L)
						L = location[z[j].s], Lid = z[j].s;
				}
			}
		}
   	}
	assert(cont <= n * (n - 1)/2);
}
/*
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 (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;
}
/*
3
6
1 3
2 4
1 1
2 2
1 5
2 6
 
 
*/

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp:108:1: warning: "/*" within comment [-Wcomment]
  108 | /**/
      |  
rail.cpp:281:1: warning: "/*" within comment [-Wcomment]
  281 | /*
      |  
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:153:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |    for(int j = 0; j < D.size(); j++) {
      |                   ~~^~~~~~~~~~
rail.cpp:146:7: warning: unused variable 'pos' [-Wunused-variable]
  146 |    ll pos = R - b;
      |       ^~~
rail.cpp:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int j = 0; j < C.size(); j++) {
      |                    ~~^~~~~~~~~~

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