oj.uz

답안 #77914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77914 2018-10-01T07:34:49 Z shoemakerjo 철로 (IOI14_rail) C++14
100 / 100
 120 ms 5644 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
#define maxm 2000010
#define pii pair<int, int>
#define C 1
#define D 2
//ooh, ooh, macros!
#define maxn 5010
int blk[maxm]; //check if something is there or not
int zdist[maxn];
int xdist[maxn];


void findLocation(int N, int first, int location[], int stype[])
{
	//just directly set location and stype
	location[0] = first;
	stype[0] = C;
	blk[first] = C;

	vector<pii> stuff;
	for (int i = 1; i < N; i++) {
		zdist[i] = getDistance(0, i);
		stuff.push_back(pii(zdist[i], i));

	}
	sort(stuff.begin(), stuff.end());
	int X= stuff[0].second;
	for (int j = 1; j < N; j++) {
		if (j != X) xdist[j] = getDistance(X, j);

	}
	location[X] = location[0] + stuff[0].first;
	stype[X] = D;
	blk[location[X]] = D;

	vector<int> onright;
	vector<int> onleft;

	for (int j = 1; j < N; j++) {
		if (j == X) continue;
		if (xdist[j] < zdist[X] && zdist[j] == zdist[X] + xdist[j]) {
			//is in middle 
			location[j] = location[X] - xdist[j] ;
			stype[j] = C;
			blk[location[j]] = C;
			// cout << j << " did this thing" << endl;
			continue;
		}
		if (zdist[X] + xdist[j] == zdist[j]) {
			// cout << j << " is on the right" << endl;
			// onright.push_back(j);
			onleft.push_back(j);
		}
		else {
			// cout << j << "  is on the left " << endl;
			// onleft.push_back(j);
			onright.push_back(j);
		}
	}

	stuff.clear(); //i love using stuff
	for (int vv : onright) {
		stuff.push_back(pii(zdist[vv], vv));
	}
	sort(stuff.begin(), stuff.end());

	if (stuff.size()) {
		int fardind = stuff[0].second;
		// cout << " fardind: " << fardind  << endl;
		location[fardind] = location[0] + stuff[0].first;
		stype[fardind] = D;
		blk[location[fardind]] = D; 
		for (int j = 1; j < stuff.size(); j++) {
			// cout << " DOING  " << vv << endl;
			int vv = stuff[j].second;
			// cout << " DOING  " << vv << endl;
			int nd = getDistance(vv, fardind);

			int z = zdist[vv] - zdist[fardind] - nd;
			z /= 2;
			z = 0-z;
			// cout  << " z :: " << z << endl;

			if (location[fardind] - z >= 0 && blk[location[fardind] - z] == D) {
				// we are a C
				stype[vv] = C;
				int nloc = location[fardind] - nd;
				location[vv] = nloc;
				blk[nloc] = C;

			} 
			else {
				//we are the new furthest d
				location[vv] = zdist[vv] + location[0];
				stype[vv] = D;
				blk[location[vv]] = D;
				fardind = vv;
			}
		}
	}

	stuff.clear();
	for (int vv : onleft) {
		// cout << vv << " is on the left" << endl;
		stuff.push_back(pii(xdist[vv], vv));
	}
	sort(stuff.begin(), stuff.end());

	if (stuff.size()) {
		int farcind = stuff[0].second;

		// cout << "farcind:   " << farcind << endl;

		location[farcind] = location[X] - stuff[0].first;
		stype[farcind] = C;
		blk[location[farcind]] = C;
		for (int j = 1; j < stuff.size(); j++) {
			int vv = stuff[j].second;
			// cout << "doing " << vv << endl;
			int nd = getDistance(vv, farcind);

			int z = xdist[vv] - xdist[farcind] - nd;
			z /= 2;
			z = 0-z;
			if (location[farcind] + z >= 0 && blk[location[farcind] + z] == C) {
				//we are a D
				stype[vv] = D;
				int nloc = location[farcind] + nd;
				location[vv] = nloc;
				blk[nloc] = D;
			}
			else {
				//we are the new furthest C
				location[vv] = location[X] - xdist[vv] ;
				stype[vv] = C;
				blk[location[vv]] = C;
				farcind = vv;
			}
		}

	}	

	//should be good to go

}
//make sure that we are correctly marking things!

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < stuff.size(); j++) {
                   ~~^~~~~~~~~~~~~~
rail.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < stuff.size(); j++) {
                   ~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 4476 KB Output is correct
2 Correct 87 ms 4588 KB Output is correct
3 Correct 87 ms 4732 KB Output is correct
4 Correct 90 ms 4732 KB Output is correct
5 Correct 87 ms 4732 KB Output is correct
6 Correct 91 ms 4732 KB Output is correct
7 Correct 87 ms 4732 KB Output is correct
8 Correct 86 ms 4732 KB Output is correct
9 Correct 86 ms 4732 KB Output is correct
10 Correct 92 ms 4896 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 4896 KB Output is correct
2 Correct 90 ms 4896 KB Output is correct
3 Correct 85 ms 4956 KB Output is correct
4 Correct 86 ms 4956 KB Output is correct
5 Correct 92 ms 4956 KB Output is correct
6 Correct 120 ms 4956 KB Output is correct
7 Correct 87 ms 4988 KB Output is correct
8 Correct 91 ms 4988 KB Output is correct
9 Correct 87 ms 5028 KB Output is correct
10 Correct 88 ms 5204 KB Output is correct
11 Correct 98 ms 5204 KB Output is correct
12 Correct 86 ms 5204 KB Output is correct
13 Correct 96 ms 5208 KB Output is correct
14 Correct 88 ms 5376 KB Output is correct
15 Correct 87 ms 5376 KB Output is correct
16 Correct 88 ms 5464 KB Output is correct
17 Correct 87 ms 5512 KB Output is correct
18 Correct 90 ms 5512 KB Output is correct
19 Correct 118 ms 5512 KB Output is correct
20 Correct 109 ms 5644 KB Output is correct