oj.uz

Submission #28214

# Submission time Handle Problem Language Result Execution time Memory
28214 2017-07-15T19:32:30 Z noobprogrammer Rail (IOI14_rail) C++14
30 / 100
 106 ms 892 KB 
#include "rail.h"
#include <bits/stdc++.h> 
using namespace std ;
#define ii  pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<ii>

int from0[5010] , from1[5010] ;
vii le , ri , D , C ; 

void findLocation(int n, int zr , int loc[], int tp[]){
	int mn = 1e9 , opt = -1 ;
	for(int i=1;i<n;i++) {
		from0[i] = getDistance(0, i) ;
		if(from0[i] < mn){
			mn = from0[i] ;
			opt = i ;
		}
	}
	from1[0] = from0[opt] ;
	loc[0] = zr ; tp[0] = 1 ;
	loc[opt] = zr + from0[opt] ; tp[opt] = 2 ;
	for(int i=1 ; i<n ;i++){
		if(i == opt) continue ;
		from1[i] = getDistance( opt , i ) ;
		if(from1[i] + from0[opt] == from0[i]){
			if(from1[i] > from0[opt]) le.push_back({i , from1[i]}) ;
			else loc[i] = loc[opt] - from1[i] , tp[i] = 1 ;
		}
		else{
			ri.push_back({i , from0[i]}) ;
		}
	}
	
	for(ii v : ri){
		if(D.empty()) {
			D.push_back(v) ;
			loc[v.fi] = loc[0] + v.se ;
			tp[v.fi] = 2 ;
		}
		else{
			ii cur = D.back() ;
			int dst = getDistance(cur.fi , v.fi) ;
			bool chk = 0 ; 
			for(ii nd : D){
				if(dst - cur.se + nd.se <= 0) continue ;
				if(nd.se + dst - cur.se + nd.se == v.se){
					tp[v.fi] = 1 ;
					loc[v.fi] = loc[nd.fi] - (dst - cur.se + nd.se) ; 
					chk = 1 ;
					break ;
				}
			}
			if(!chk) {
				D.push_back(v) ;
				loc[v.fi] = loc[0] + v.se ;
				tp[v.fi] = 2 ;
			}
		}
	}

	D.clear() ; 
	for(ii v : le){
		if(D.empty()) {
			D.push_back(v) ;
			loc[v.fi] = loc[opt] - v.se ;
			tp[v.fi] = 1 ;
		}
		else{
			ii cur = D.back() ;
			int dst = getDistance(cur.fi , v.fi) ;
			bool chk = 0 ; 
			for(ii nd : D){
				if(dst - cur.se + nd.se <= 0) continue ;
				if(nd.se + dst - cur.se + nd.se == v.se){
					tp[v.fi] = 2 ;
					loc[v.fi] = loc[nd.fi] + (dst - cur.se + nd.se) ; 
					chk = 1 ;
					break ;
				}
			}
			if(!chk) {
				D.push_back(v) ;
				loc[v.fi] = loc[opt] - v.se ;
				tp[v.fi] = 1 ;
			}
		}
	}
	// for(int i=0;i<n;i++) printf("%d %d\n" , loc[i] , tp[i]) ;
	return ; 
}


// /* 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;
// }


// void getInput()
// {
//   freopen("in.txt" , "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 (i = 0; i < S; i++){
//     // printf("%d %d\n" , location[i] , type[i]) ;
//     if(type[i]!=stations[i].type || location[i]!=stations[i].location)
//       ok = 0;
//   }
//   if(ok==0)	printf("Incorrect");
//   else	printf("Correct");
//   return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 2 ms 544 KB Output is correct
10 Correct 2 ms 544 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Correct 2 ms 544 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 2 ms 668 KB Output is correct
6 Correct 2 ms 668 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 892 KB Output isn't correct
2 Halted 0 ms 0 KB -