oj.uz

답안 #254289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254289 2020-07-29T18:18:21 Z b00n0rp 철로 (IOI14_rail) C++17
100 / 100
 90 ms 760 KB 
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define all(v) v.begin(),v.end()

#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

int dist[3][5005];

vector<pii> cees,dees;

void findLocation(int N, int first, int location[], int stype[]){
	FOR(i,1,N){
		dist[0][i] = getDistance(i,0);
	}
	int mn = 1;
	FOR(i,1,N){
		if(dist[0][mn] > dist[0][i]) mn = i;
	}
	FOR(i,1,N){
		if(i != mn) dist[1][i] = getDistance(mn,i);
	}
	
	location[0] = first;
	stype[0] = 1;
	location[mn] = first+dist[0][mn];
	stype[mn] = 2;

	vector<pii> lft,rgt;
	FOR(i,1,N){
		if(i != mn){
			// trace(i,dist[0][i],dist[1][i]);
			if(dist[0][i] == dist[0][mn]+dist[1][i]) lft.pb({dist[1][i],i});
			else rgt.pb({dist[0][i],i});
		}
	}
	sort(all(lft));
	sort(all(rgt));

	// trace(mn);

	int prevC = 0,prevD = mn;
	cees.pb({-first,0});
	dees.pb({location[mn],mn});
	for(auto x:lft){
		// trace(x.S);
		location[x.S] = location[prevC]+getDistance(prevC,x.S);
		stype[x.S] = 2;
		// trace(location[x.S]);
		int closest = cees[lower_bound(all(cees),make_pair(-location[x.S],-1))-cees.begin()].S;
		// trace(closest);
		if(location[x.S]-location[closest]+dist[1][closest] != dist[1][x.S]){
			location[x.S] = location[mn]-dist[1][x.S];
			stype[x.S] = 1;
			cees.pb({-location[x.S],x.S});
			prevC = x.S;
		}
		// trace(stype[x.S],location[x.S]);
	}
	for(auto x:rgt){
		location[x.S] = location[prevD]-getDistance(prevD,x.S);
		stype[x.S] = 1;
		int closest = dees[lower_bound(all(dees),make_pair(location[x.S],-1))-dees.begin()].S;
		if(location[closest]-location[x.S]+dist[0][closest] != dist[0][x.S]){
			location[x.S] = location[0]+dist[0][x.S];
			stype[x.S] = 2;
			dees.pb({location[x.S],x.S});
			prevD = x.S;
		}
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 588 KB Output is correct
2 Correct 76 ms 508 KB Output is correct
3 Correct 76 ms 636 KB Output is correct
4 Correct 78 ms 632 KB Output is correct
5 Correct 79 ms 632 KB Output is correct
6 Correct 78 ms 636 KB Output is correct
7 Correct 75 ms 632 KB Output is correct
8 Correct 76 ms 640 KB Output is correct
9 Correct 77 ms 636 KB Output is correct
10 Correct 76 ms 632 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 588 KB Output is correct
2 Correct 77 ms 632 KB Output is correct
3 Correct 81 ms 632 KB Output is correct
4 Correct 78 ms 632 KB Output is correct
5 Correct 76 ms 632 KB Output is correct
6 Correct 76 ms 632 KB Output is correct
7 Correct 76 ms 632 KB Output is correct
8 Correct 74 ms 632 KB Output is correct
9 Correct 85 ms 636 KB Output is correct
10 Correct 90 ms 632 KB Output is correct
11 Correct 74 ms 760 KB Output is correct
12 Correct 74 ms 636 KB Output is correct
13 Correct 76 ms 632 KB Output is correct
14 Correct 83 ms 632 KB Output is correct
15 Correct 77 ms 632 KB Output is correct
16 Correct 76 ms 644 KB Output is correct
17 Correct 77 ms 760 KB Output is correct
18 Correct 75 ms 636 KB Output is correct
19 Correct 79 ms 632 KB Output is correct
20 Correct 77 ms 632 KB Output is correct