oj.uz

답안 #799842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799842 2023-08-01T06:12:03 Z tolbi 철로 (IOI14_rail) C++17
100 / 100
 85 ms 98524 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it<<" ";return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it<<" ";return os;}
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1ll<<((int)(bi)))
typedef long long ll;
#include "rail.h"
const ll INF = LONG_LONG_MAX;
const ll MOD = 1e9+9;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
int dst[5000][5000];
int dist(int a, int b){
	if (a==b){
		return dst[a][b]=0;
	}
	if (dst[a][b]==-1){
		dst[a][b]=dst[b][a]=getDistance(a,b);
	}
	return dst[a][b];
}
void findLocation(int n, int __first, int pl[], int type[])
{
	for (int i = 0; i < 5000; i++){
		for (int j = 0; j < 5000; j++){
			dst[i][j]=-1;
		}
		dst[i][i]=0;
	}
	vector<int> arr(n-1);
	iota(arr.begin(), arr.end(), 1);
	sort(arr.begin(), arr.end(), [&](int a, int b){
		return dist(0,a)<dist(0,b);
	});
	vector<int> leftte;
	vector<int> rightta;
	int right = arr[0];
	type[0]=1;
	type[right]=2;
	pl[0]=__first;
	pl[right]=pl[0]+dist(0,right);
	for (int i = 1; i < arr.size(); i++){
		int k = arr[i];
		if (dist(0,k)==dist(0,right)+dist(k,right) && dist(k,right)<dist(0,right)){
			type[k]=1;
			pl[k]=pl[right]-dist(k,right);
			continue;
		}
		if (dist(0,k)==dist(0,right)+dist(k,right)){
			leftte.push_back(k);
		}
		else {
			rightta.push_back(k);
		}
	}
	int D = right;
	int left = 0;
	set<int> st;
	st.insert(pl[right]);
	for (int i = 0; i < rightta.size(); i++){
		int k = rightta[i];
		int tot = pl[right]-pl[left]+dist(right,k);
		if ((tot-dist(left,k))%2==0 && st.find(pl[right]-(tot-dist(left,k))/2)!=st.end()){
			type[k]=1;
			pl[k]=pl[right]-dist(right,k);
		}
		else {
			type[k]=2;
			pl[k]=pl[left]+dist(left,k);
			st.insert(pl[k]);
			right=k;
		}
	}
	st.clear();
	st.insert(pl[left]);
	right=D;
	for (int i = 0; i < leftte.size(); i++){
		int k = leftte[i];
		int tot = pl[right]-pl[left]+dist(left,k);
		if ((tot-dist(right,k))%2==0 && st.find(pl[left]+(tot-dist(right,k))/2)!=st.end()){
			type[k]=2;
			pl[k]=pl[left]+dist(left, k);
		}
		else {
			type[k]=1;
			pl[k]=pl[right]-dist(right,k);
			st.insert(pl[k]);
			left=k;
		}
	}
}

Compilation message

rail.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 1; i < arr.size(); i++){
      |                  ~~^~~~~~~~~~~~
rail.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i < rightta.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
rail.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < leftte.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 98124 KB Output is correct
2 Correct 36 ms 98236 KB Output is correct
3 Correct 56 ms 98124 KB Output is correct
4 Correct 34 ms 98140 KB Output is correct
5 Correct 33 ms 98180 KB Output is correct
6 Correct 33 ms 98208 KB Output is correct
7 Correct 34 ms 98156 KB Output is correct
8 Correct 34 ms 98260 KB Output is correct
9 Correct 34 ms 98124 KB Output is correct
10 Correct 33 ms 98232 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 98228 KB Output is correct
2 Correct 32 ms 98204 KB Output is correct
3 Correct 34 ms 98124 KB Output is correct
4 Correct 33 ms 98108 KB Output is correct
5 Correct 33 ms 98180 KB Output is correct
6 Correct 33 ms 98216 KB Output is correct
7 Correct 33 ms 98160 KB Output is correct
8 Correct 34 ms 98176 KB Output is correct
9 Correct 34 ms 98208 KB Output is correct
10 Correct 33 ms 98200 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 98380 KB Output is correct
2 Correct 79 ms 98404 KB Output is correct
3 Correct 78 ms 98396 KB Output is correct
4 Correct 79 ms 98400 KB Output is correct
5 Correct 79 ms 98380 KB Output is correct
6 Correct 80 ms 98400 KB Output is correct
7 Correct 85 ms 98432 KB Output is correct
8 Correct 79 ms 98444 KB Output is correct
9 Correct 79 ms 98464 KB Output is correct
10 Correct 79 ms 98448 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 98392 KB Output is correct
2 Correct 79 ms 98412 KB Output is correct
3 Correct 76 ms 98388 KB Output is correct
4 Correct 82 ms 98328 KB Output is correct
5 Correct 78 ms 98400 KB Output is correct
6 Correct 79 ms 98404 KB Output is correct
7 Correct 82 ms 98380 KB Output is correct
8 Correct 79 ms 98436 KB Output is correct
9 Correct 79 ms 98452 KB Output is correct
10 Correct 79 ms 98372 KB Output is correct
11 Correct 78 ms 98428 KB Output is correct
12 Correct 80 ms 98428 KB Output is correct
13 Correct 81 ms 98380 KB Output is correct
14 Correct 79 ms 98436 KB Output is correct
15 Correct 78 ms 98444 KB Output is correct
16 Correct 79 ms 98424 KB Output is correct
17 Correct 79 ms 98428 KB Output is correct
18 Correct 78 ms 98452 KB Output is correct
19 Correct 82 ms 98524 KB Output is correct
20 Correct 77 ms 98444 KB Output is correct