oj.uz

Submission #59082

# Submission time Handle Problem Language Result Execution time Memory
59082 2018-07-20T12:57:44 Z WA_TLE Rail (IOI14_rail) C++14
100 / 100
 107 ms 2904 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
#define loc location
#include"rail.h"
void findLocation(int n,int first,int location[],int stype[]){
	//まず最遠点(一番左にある点)をもとめる
	//そこからの距離をすべて調べる
	//のこり(n-1)回ですべてが求まる
	if(n==1){loc[0]=first;stype[0]=1;return;}
	int i;
	vector<pair<int,int>>dis(n-1);
	for(i=1;i<n;i++){dis[i-1]=mp(getDistance(0,i),i);}
	SO(dis);
	vector<int>bas(n);
	map<int,int>aru;
	int hi=0,mg=dis[0].sec,hiba=first,mgba=first+dis[0].fir;
	loc[0]=first;loc[mg]=first+dis[0].fir;
	stype[0]=1;stype[mg]=2;
	aru[hiba]=1;
	aru[mgba]=2;
	for(i=1;i<n-1;i++){
		int ter=dis[i].sec;
		int lefdi=getDistance(hi,ter);
		int rigdi=getDistance(mg,ter);
		int chu=(hiba+lefdi+mgba-rigdi)/2;
		int doti,bas;
		if(chu<=first){if(aru[chu]==1){doti=1;}else{doti=2;}}
		else{if(aru[chu]==2){doti=2;}else{doti=1;}}
		if(doti==1){
			stype[ter]=2;loc[ter]=hiba+lefdi;aru[loc[ter]]=2;
			if(maxeq(mgba,loc[ter])){mg=ter;}
		}else{
			stype[ter]=1;loc[ter]=mgba-rigdi;aru[loc[ter]]=1;
			if(mineq(hiba,loc[ter])){hi=ter;}
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:75:12: warning: unused variable 'bas' [-Wunused-variable]
   int doti,bas;
            ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 356 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 0 ms 804 KB Output is correct
10 Correct 2 ms 936 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1580 KB Output is correct
2 Correct 98 ms 1580 KB Output is correct
3 Correct 85 ms 1580 KB Output is correct
4 Correct 89 ms 1580 KB Output is correct
5 Correct 85 ms 1680 KB Output is correct
6 Correct 91 ms 1680 KB Output is correct
7 Correct 87 ms 1680 KB Output is correct
8 Correct 86 ms 1708 KB Output is correct
9 Correct 89 ms 1728 KB Output is correct
10 Correct 92 ms 1772 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1956 KB Output is correct
2 Correct 100 ms 1992 KB Output is correct
3 Correct 95 ms 2024 KB Output is correct
4 Correct 86 ms 2072 KB Output is correct
5 Correct 88 ms 2120 KB Output is correct
6 Correct 100 ms 2160 KB Output is correct
7 Correct 94 ms 2280 KB Output is correct
8 Correct 96 ms 2376 KB Output is correct
9 Correct 100 ms 2420 KB Output is correct
10 Correct 90 ms 2464 KB Output is correct
11 Correct 86 ms 2512 KB Output is correct
12 Correct 104 ms 2552 KB Output is correct
13 Correct 96 ms 2552 KB Output is correct
14 Correct 107 ms 2552 KB Output is correct
15 Correct 93 ms 2564 KB Output is correct
16 Correct 88 ms 2600 KB Output is correct
17 Correct 105 ms 2644 KB Output is correct
18 Correct 99 ms 2688 KB Output is correct
19 Correct 105 ms 2860 KB Output is correct
20 Correct 89 ms 2904 KB Output is correct