oj.uz

Submission #857809

# Submission time Handle Problem Language Result Execution time Memory
857809 2023-10-07T02:54:06 Z sunwukong123 Rail (IOI14_rail) C++14
100 / 100
 54 ms 1348 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 5005;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<pi> vec;
int D[MAXN];
map<int,int>tt;
void findLocation(int n, int first, int loc[], int stype[])
{
	for(int i=1;i<n;i++){
		D[i]=getDistance(0,i);
		vec.push_back({D[i],i});
	}
	sort(vec.begin(),vec.end());
	stype[0]=tt[0]=1;
	stype[vec[0].second]=tt[vec[0].first]=2;
	loc[vec[0].second]=vec[0].first;
	int R=vec[0].second;
	int L=0;
	for(int i=1;i<(int)vec.size();i++){
		int idx=vec[i].second;
		int d1=getDistance(idx,R);
		int d2=getDistance(idx,L);
		//debug(vec[i].second,d1,d2);
		bool c1=0,c2=0;
		int ww=loc[R]-d1;
		int p=ww+(D[idx]-ww)/2;
		if(ww<0){
			p=(D[idx]-abs(ww))/2;
		}
		if(tt[ww] == 0 && ((D[idx]-abs(ww)) % 2 == 0) && (D[idx]-abs(ww)>0) && tt[p] == 2){
			c1=1;
		}

		ww=loc[L]+d2;
		int dd=D[idx]-2*vec[0].first;
		p=ww-(dd-abs(ww))/2;
		if(tt[ww] == 0 && ww<0 && (dd-abs(ww))%2 == 0 && (dd-abs(ww))>0 && tt[p]==1){
			c2=1;
		}
		//debug(c1,c2);
		if(c1&&!c2){
			loc[idx]=loc[R]-d1;
			stype[idx] = tt[loc[idx]] = 1;
			if(loc[idx] < loc[L])L=idx;
		}
		if(!c1&&!c2){
			loc[idx]=loc[L]+d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}
		if(c1&&c2){
			loc[idx]=loc[L] + d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}
		if(!c1 && c2){
			loc[idx]=loc[L] + d2;
			stype[idx]=tt[loc[idx]] = 2;
			if(loc[idx]>loc[R])R=idx;
		}

	}
	
	for(int i=0;i<n;i++){
		loc[i]+=first;
	}
	/*
	for(int i=0;i<n;i++){
		cerr<<stype[i]<<" ";
	}
	cerr<<"\n";
	for(int i=0;i<n;i++){
		cerr<<loc[i]<<" ";
	}
	cerr<<"\n\n\n";
	*/
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 432 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1128 KB Output is correct
2 Correct 50 ms 1148 KB Output is correct
3 Correct 47 ms 1164 KB Output is correct
4 Correct 54 ms 1104 KB Output is correct
5 Correct 51 ms 1108 KB Output is correct
6 Correct 50 ms 1168 KB Output is correct
7 Correct 51 ms 1164 KB Output is correct
8 Correct 48 ms 1164 KB Output is correct
9 Correct 49 ms 1152 KB Output is correct
10 Correct 50 ms 1152 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1108 KB Output is correct
2 Correct 48 ms 1148 KB Output is correct
3 Correct 48 ms 1168 KB Output is correct
4 Correct 50 ms 1148 KB Output is correct
5 Correct 50 ms 1108 KB Output is correct
6 Correct 47 ms 1108 KB Output is correct
7 Correct 53 ms 1108 KB Output is correct
8 Correct 53 ms 1168 KB Output is correct
9 Correct 48 ms 1032 KB Output is correct
10 Correct 50 ms 1164 KB Output is correct
11 Correct 47 ms 1104 KB Output is correct
12 Correct 49 ms 1148 KB Output is correct
13 Correct 49 ms 1108 KB Output is correct
14 Correct 47 ms 1112 KB Output is correct
15 Correct 47 ms 1152 KB Output is correct
16 Correct 48 ms 1148 KB Output is correct
17 Correct 50 ms 1164 KB Output is correct
18 Correct 47 ms 1156 KB Output is correct
19 Correct 50 ms 1104 KB Output is correct
20 Correct 53 ms 1348 KB Output is correct