oj.uz

Submission #130367

# Submission time Handle Problem Language Result Execution time Memory
130367 2019-07-15T04:39:58 Z antimirage Rail (IOI14_rail) C++14
100 / 100
 93 ms 760 KB 
#include "rail.h"
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 5005; 
 
int dist[2][N], first;
 
vector <int> lft, op, cl;
 
bool cmp1 (int a, int b) {
	return dist[0][a] < dist[0][b];
}
void findLocation(int n, int pos, int a[], int t[])
{
	int mn = 1e9 + 7, ind;
	a[0] = pos, t[0] = 1;
	
	for (int i = 1; i < n; i++) {	
		dist[0][i] = getDistance(0, i);
		if (dist[0][i] < mn) {
			mn = dist[0][i];
			ind = i;
		}
	//	cout << i << " -> " << dist[0][i] << endl;
	}
	a[ind] = pos + mn; t[ind] = 2;
	
	int L = 0, R = ind;
	
	for (int i = 1; i < n; i++) {
		if (i == ind) continue;
		lft.pb(i);
	}
	sort(all(lft), cmp1);
	
	op.pb(L);
	cl.pb(R);
	
	for (auto it : lft) {
	//	cout << it << endl;
		int res1 = getDistance(L, it);
		int res2 = getDistance(R, it);
		pos = a[L] + res1;
		
		if (pos < a[0]) {
			for (auto i : op) {
				if (a[i] < pos && res2 == (a[R] - a[i]) + pos - a[i]) {
					a[it] = pos;
					t[it] = 2;
					cl.pb(it);
					break;
				}
			}
		}
		if (t[it]) continue;
			
		pos = a[R] - res2;
		
		if (pos > a[0]) {
			for (auto i : cl) {
				if (a[i] > pos && res1 == (a[i] - a[L]) + a[i] - pos) {
					a[it] = pos;
					t[it] = 1;
					op.pb(it);
					break;
				}
			}
		}
		if (t[it]) continue;
		
		if (dist[0][it] == dist[0][ind] + a[ind] - pos) {
			op.pb(it);
			t[it] = 1;
			a[it] = pos;
			L = it;
		} else {
			cl.pb(it);
			t[it] = 2;
			a[it] = a[L] + res1;
			R = it;
		}
	}
	/**cout << "\nasd\n";
	for (int i = 0; i < n; i++) {
		cout << i << " ==> " << a[i] << " " << t[i] << endl;
	}**/
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:34:7: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
  a[ind] = pos + mn; t[ind] = 2;
       ^

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 676 KB Output is correct
2 Correct 89 ms 760 KB Output is correct
3 Correct 89 ms 640 KB Output is correct
4 Correct 89 ms 548 KB Output is correct
5 Correct 89 ms 632 KB Output is correct
6 Correct 90 ms 552 KB Output is correct
7 Correct 90 ms 632 KB Output is correct
8 Correct 88 ms 644 KB Output is correct
9 Correct 90 ms 640 KB Output is correct
10 Correct 93 ms 632 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 604 KB Output is correct
2 Correct 90 ms 760 KB Output is correct
3 Correct 89 ms 632 KB Output is correct
4 Correct 88 ms 732 KB Output is correct
5 Correct 88 ms 632 KB Output is correct
6 Correct 90 ms 760 KB Output is correct
7 Correct 91 ms 760 KB Output is correct
8 Correct 88 ms 632 KB Output is correct
9 Correct 89 ms 632 KB Output is correct
10 Correct 89 ms 636 KB Output is correct
11 Correct 88 ms 632 KB Output is correct
12 Correct 88 ms 732 KB Output is correct
13 Correct 89 ms 760 KB Output is correct
14 Correct 91 ms 760 KB Output is correct
15 Correct 89 ms 632 KB Output is correct
16 Correct 89 ms 732 KB Output is correct
17 Correct 89 ms 636 KB Output is correct
18 Correct 91 ms 760 KB Output is correct
19 Correct 92 ms 632 KB Output is correct
20 Correct 91 ms 632 KB Output is correct