oj.uz

답안 #296292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
296292 2020-09-10T13:15:18 Z nvmdava 철로 (IOI14_rail) C++17
100 / 100
 128 ms 776 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int d[5005][3];
vector<pair<int, int> > rh, lh;

int lo[5005], st[5005];

vector<int> bruh;

void solve(int con, int flip, vector<pair<int, int> >& v){
	sort(v.begin(), v.end());
	bruh.clear();
	int r = -1;
	for(auto& x : v){

		bool ok = 0;
		int d;
		if(r == -1)
			ok = 1;
		else {
			d = lo[r] - getDistance(r, x.ss);
			if(d != 2 * (*lower_bound(bruh.begin(), bruh.end(), d)) - x.ff)
				ok = 1; 
		}

		if(ok){
			lo[r = x.ss] = x.ff;
			st[r] = 1;
			bruh.push_back(x.ff);
		} else {
			lo[x.ss] = d;
			st[x.ss] = -1;
		}
	}
	for(auto& x : v){
		st[x.ss] *= flip;
		lo[x.ss] = con + flip * lo[x.ss];
	}
}

void findLocation(int N, int first, int location[], int stype[]){
	int le, ri;
	int n = N;
	le = 0;
	int tt = 2000000;

	if(n == 1){
		location[0] = first;
		stype[0] = 1;
		return;
	}

	for(int i = 0; i < n; ++i){
		if(le == i)
			continue;
		d[i][0] = getDistance(le, i);
		if(d[i][0] < tt){
			ri = i;
			tt = d[i][0];
		}
	}
	tt = 2000000;
	for(int i = 0; i < n; ++i){
		if(ri == i) continue;
		d[i][1] = getDistance(ri, i);
		if(d[i][1] < tt){
			le = i;
			tt = d[i][1];
		}
	}
	
	lo[ri] = first + d[ri][0];
	st[ri] = 1;

	lo[le] = lo[ri] - d[le][1];
	st[le] = -1;

	d[0][0] = 2 * d[ri][0];
	d[ri][1] = 2 * d[le][1];

	for(int i = 0; i < n; ++i){
		if(le == i || ri == i) continue;

		if(d[i][0] == d[i][1] + d[ri][0])
			rh.push_back({d[i][1], i});
		else
			lh.push_back({d[i][0] - (d[ri][0] - d[le][1]), i});
	}
	solve(lo[le], 1, lh);
	solve(lo[ri], -1, rh);
	for(int i = 0; i < n; ++i){
		location[i] = lo[i];
		stype[i] = (st[i] == 1 ? 2 : 1);
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:75:26: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |  lo[ri] = first + d[ri][0];
      |                   ~~~~~~~^

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 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 1 ms 384 KB Output is correct
2 Correct 1 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 1 ms 384 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 632 KB Output is correct
2 Correct 85 ms 760 KB Output is correct
3 Correct 85 ms 632 KB Output is correct
4 Correct 85 ms 632 KB Output is correct
5 Correct 83 ms 760 KB Output is correct
6 Correct 85 ms 776 KB Output is correct
7 Correct 84 ms 632 KB Output is correct
8 Correct 83 ms 760 KB Output is correct
9 Correct 83 ms 632 KB Output is correct
10 Correct 87 ms 632 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 604 KB Output is correct
2 Correct 96 ms 636 KB Output is correct
3 Correct 105 ms 632 KB Output is correct
4 Correct 88 ms 652 KB Output is correct
5 Correct 101 ms 760 KB Output is correct
6 Correct 84 ms 760 KB Output is correct
7 Correct 84 ms 632 KB Output is correct
8 Correct 109 ms 632 KB Output is correct
9 Correct 100 ms 632 KB Output is correct
10 Correct 97 ms 632 KB Output is correct
11 Correct 83 ms 632 KB Output is correct
12 Correct 84 ms 632 KB Output is correct
13 Correct 86 ms 632 KB Output is correct
14 Correct 88 ms 632 KB Output is correct
15 Correct 83 ms 652 KB Output is correct
16 Correct 85 ms 632 KB Output is correct
17 Correct 128 ms 648 KB Output is correct
18 Correct 93 ms 632 KB Output is correct
19 Correct 97 ms 632 KB Output is correct
20 Correct 87 ms 632 KB Output is correct