oj.uz

Submission #245886

# Submission time Handle Problem Language Result Execution time Memory
245886 2020-07-07T16:45:04 Z Fasho Rail (IOI14_rail) C++14
100 / 100
 200 ms 764 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
 
#include "rail.h"
 
void findLocation(int N, int first, int location[], int stype[]) {
	auto fix = [&](int i, int pos, int type) {
		location[i] = pos;
		stype[i] = type;
	};
	REP(i, N) fix(i, -1, -1);
 
	fix(0, first, 1);
	vector<pair<int, int>> stations;
	FOR(i, 1, N - 1)
		stations.emplace_back(getDistance(0, i), i);	
 
	sort(stations.begin(), stations.end());
 
	int L = 0, R = stations[0].second;
	fix(R, first + stations[0].first, 2);
	stations.erase(stations.begin());
 
	for(auto &[d, i] : stations) {
		int a = getDistance(L, i);
		int b = getDistance(R, i);
 
		{ // [)]
			bool ok = false;
			int pos = location[L] + a;
			REP(j, N) {
				if(stype[j] == 1) {
					if(location[R] + pos - 2 * location[j] == b)
						ok = true;
				}
			}
			if(ok) {
				fix(i, pos, 2);
				if(location[R] < pos) R = i;
				continue;
			}
		}
		{ // (
			int pos = location[R] - b;
			bool ok = false;
			REP(j, N) {
				if(stype[j] == 2) {
					if(location[j] * 2 - pos - location[0] == d)
						ok = true;
				}
			}
			if(ok) {
				fix(i, pos, 1);
				if(pos < location[L]) L = i;
				continue;
			}
		}
		{ // [])
			int pos = location[L] + a;
			fix(i, pos, 2);
			R = i;
		}
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:27:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto &[d, i] : stations) {
            ^

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 632 KB Output is correct
2 Correct 182 ms 764 KB Output is correct
3 Correct 189 ms 632 KB Output is correct
4 Correct 182 ms 636 KB Output is correct
5 Correct 186 ms 632 KB Output is correct
6 Correct 188 ms 668 KB Output is correct
7 Correct 189 ms 632 KB Output is correct
8 Correct 188 ms 632 KB Output is correct
9 Correct 188 ms 632 KB Output is correct
10 Correct 186 ms 760 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 632 KB Output is correct
2 Correct 183 ms 632 KB Output is correct
3 Correct 182 ms 632 KB Output is correct
4 Correct 191 ms 632 KB Output is correct
5 Correct 191 ms 632 KB Output is correct
6 Correct 187 ms 636 KB Output is correct
7 Correct 188 ms 636 KB Output is correct
8 Correct 182 ms 632 KB Output is correct
9 Correct 187 ms 632 KB Output is correct
10 Correct 185 ms 636 KB Output is correct
11 Correct 200 ms 632 KB Output is correct
12 Correct 184 ms 632 KB Output is correct
13 Correct 193 ms 632 KB Output is correct
14 Correct 182 ms 760 KB Output is correct
15 Correct 185 ms 632 KB Output is correct
16 Correct 183 ms 632 KB Output is correct
17 Correct 185 ms 636 KB Output is correct
18 Correct 181 ms 696 KB Output is correct
19 Correct 185 ms 632 KB Output is correct
20 Correct 194 ms 632 KB Output is correct