Submission #599996

#	Time	Username	Problem	Language	Result	Execution time	Memory
599996		8e7	Rail (IOI14_rail)	C++17	100 / 100	80 ms	1612 KiB

rail

//Challenge: Accepted
#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;

bool found[maxn];
void findLocation(int N, int first, int location[], int stype[]) {
	vector<int> dl(N, 0), dr(N, 0);
	dl[0] = inf;
	for (int i = 1;i < N;i++) {
		dl[i] = getDistance(0, i);
	}
	location[0] = first;
	stype[0] = 1;
	if (N == 1) return;

	int rid = min_element(dl.begin(), dl.end()) - dl.begin();
	dr[rid] = inf;
	int llen = dl[rid];
	location[rid] = first + dl[rid];
	stype[rid] = 2;

	vector<pii> vl, vr;
	debug("rid", rid);
	for (int i = 0;i < N;i++) {
		if (i != rid) {
			dr[i] = getDistance(rid, i);
			if (!i) continue;
			if (dl[i] - dr[i] == llen) {
				if (dr[i] < llen) {
					location[i] = location[rid] - dr[i];
					stype[i] = 1;
				} else {
					vl.push_back({dr[i], i});
				}
				debug("lef", i);
			}
		}	
	}		
	int lid = min_element(dr.begin(), dr.end()) - dr.begin();	
	for (int i = 0;i < N;i++) {
		if (i == rid) dl[i] = dr[lid];
		else if (i && dl[i] - dr[i] != llen) {
			debug("rig", i);
			dl[i] = dr[i] - dr[lid];
			vr.push_back({dl[i], i});
		}
	}
	debug("lid", lid, "rid", rid);
	sort(vl.begin(), vl.end()), sort(vr.begin(), vr.end());

	int lef = 0, rig = rid;
	for (auto [dis, id]:vl) {
		int p = getDistance(lef, id), guess = location[lef] + p;
		int x = (dis - (location[rid] - guess)) / 2;
		if (guess - x >= 0 && found[guess - x]) {
			location[id] = guess;
			stype[id] = 2;
		} else {
			location[id] = location[rid] - dis;
			found[location[id]] = 1;
			stype[id] = 1;
			lef = id;
		}
	}
	for (auto [dis, id]:vr) {
		int p = getDistance(rig, id), guess = location[rig] - p;
		int x = (dis - (guess - location[lid])) / 2;
		if (guess + x < maxn && found[guess + x]) {
			location[id] = guess;
			stype[id] = 1;
		} else {
			location[id] = location[lid] + dis;
			found[location[id]] = 1;
			stype[id] = 2;
			rig = id;
		}
	}
	pary(stype,stype + N);
	pary(location, location + N);
}
/*

2 7
1 30
2 31
1 17
1 20
2 21
2 22
2 23
*/

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
rail.cpp:41:2: note: in expansion of macro 'debug'
   41 |  debug("rid", rid);
      |  ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
rail.cpp:53:5: note: in expansion of macro 'debug'
   53 |     debug("lef", i);
      |     ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
rail.cpp:61:4: note: in expansion of macro 'debug'
   61 |    debug("rig", i);
      |    ^~~~~
rail.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 0
      |                    ^
rail.cpp:66:2: note: in expansion of macro 'debug'
   66 |  debug("lid", lid, "rid", rid);
      |  ^~~~~
rail.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
rail.cpp:96:2: note: in expansion of macro 'pary'
   96 |  pary(stype,stype + N);
      |  ^~~~
rail.cpp:14:19: warning: statement has no effect [-Wunused-value]
   14 | #define pary(...) 0
      |                   ^
rail.cpp:97:2: note: in expansion of macro 'pary'
   97 |  pary(location, location + N);
      |  ^~~~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44