oj.uz

답안 #577691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577691 2022-06-15T08:08:15 Z Mazaalai 철로 (IOI14_rail) C++17
30 / 100
 75 ms 468 KB 
#include "rail.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;

// getDistance(int a, int b)
void findLocation(int n, int first, int location[], int stype[]) {
	// find closest;
	int d[2][n];
	int closest = 1, A = 0, B, C;
	for (int i = 1; i < n; i++) {
		d[0][i] = getDistance(A, i);
		if (d[0][i] < d[0][closest]) closest = i;
	}
	B = closest;
	int second = first + d[0][B];
	stype[A] = 1, location[A] = first;
	stype[B] = 2, location[B] = second;
	d[1][A] = d[0][B];
	for (int i = 1; i < n; i++) {
		if (i == B) continue;
		d[1][i] = getDistance(B, i);
	}
	vector <PII> left, right;
	int dist = d[0][B];
	for (int i = 1; i < n; i++) {
		if (i == B) continue;
		if (min(d[0][i], d[1][i]) < dist) {
			if (d[0][i] < d[1][i]) 
				stype[i] = 2, location[i] = first + d[0][i];
			else 
				stype[i] = 1, location[i] = second - d[1][i];
			continue;
		}
		if (d[0][i] < d[1][i]) right.pb({d[0][i], i});
		else left.pb({d[1][i], i});
	}
	sort(ALL(left));
	sort(ALL(right));
	// cout << "right: ";
	if (!right.empty()) {
		// for (auto el : right) cout << el.ss << ' ';
		int par = right[0].ss;
		stype[par] = 2, location[par] = first + d[0][par];
		for (int i = 1; i < right.size(); i++) {
			int dist, j; tie(dist, j) = right[i];
			int cur = getDistance(par, j);
			if (d[0][j] == d[0][par] + cur)
				stype[j] = 1, location[j] = location[par] - cur;
			else 
				stype[j] = 2, location[j] = location[A] + d[0][j], par = j;

		}
	}
	// cout << '\n';
	// cout << "left: ";
	if (!left.empty()) {
		// for (auto el : left) cout << el.ss << "," << el.ff << ' ';
		int par = left[0].ss;
		stype[par] = 1, location[par] = second - d[1][par];
		for (int i = 1; i < left.size(); i++) {
			int dist, j; tie(dist, j) = left[i];
			int cur = getDistance(par, j);
			if (d[1][j] == d[1][par] + cur)
				stype[j] = 2, location[j] = location[par] + cur;
			else 
				stype[j] = 1, location[j] = location[B] - d[1][j], par = j;

		}
	}
	// cout << '\n';
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 1; i < right.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~
rail.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i = 1; i < left.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
rail.cpp:14:29: warning: unused variable 'C' [-Wunused-variable]
   14 |  int closest = 1, A = 0, B, C;
      |                             ^

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -