oj.uz

Submission #427305

# Submission time Handle Problem Language Result Execution time Memory
427305 2021-06-14T14:09:04 Z frodakcin Rail (IOI14_rail) C++17
100 / 100
 104 ms 792 KB 
#include "rail.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>

const int INF = 0x3f3f3f3f;

bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}

struct appl // apparent location
{
	public:
		int i, x;
		appl(int _i=-1, int _x=0): i(_i), x(_x) {}
		bool operator < (const appl& o) const {return x < o.x;}
		bool operator > (const appl& o) const {return x > o.x;}
};

void findLocation(int N, int first, int location[], int stype[])
{
	int A=0, B, bestd=INF;
	std::map<int, int> map;
	auto add=[&](int u){map[location[u]]=stype[u];};
	std::vector<int> da(N), db(N);
	for(int i=1;i<N;++i)
	{
		da[i]=getDistance(A, i);
		if(ckmin(bestd, da[i]))
			B=i;
	}

	location[A] = first;
	stype[A] = 1;
	add(A);
	location[B] = first + da[B];
	stype[B] = 2;
	add(B);

	std::vector<appl> left, right;
	int AB = da[B];
	int dbmin = da[B];
	for(int i=0;i<N;++i)
		if(i != A && i != B)
		{
			db[i] = getDistance(B, i);
			ckmin(dbmin, db[i]);
			if(db[i] == da[i]-AB && db[i] < AB)
				location[i] = location[B]-db[i], stype[i]=1, add(i);
			else // outside range: to left or to right?
			{
				if(db[i] == da[i]-AB) // left
					left.push_back({i, location[B]-db[i]});
				else
					right.push_back({i, location[A]+da[i]});
			}
		}
	std::sort(left.begin(), left.end(), std::greater<appl>());
	std::sort(right.begin(), right.end());

	{
		appl prev(-1,0);
		int v;
		auto it = map.end();
		for(auto n:left)
		{
			bool ok=0;
			if(prev.i==-1 ||
					(v=getDistance(prev.i, n.i))+prev.x >= location[A] ||
					(it=map.find((v+prev.x+n.x)/2))==map.end() || // always even
					it->second != 1)
			{
				prev=n;
				location[n.i]=n.x;
				stype[n.i]=1;
				add(n.i);
			}
			else
			{
				location[n.i]=prev.x+v;
				stype[n.i]=2;
				add(n.i);
			}
		}
	}

	{
		appl prev(-1,0);
		int v;
		auto it=map.end();
		for(auto n:right)
			if(prev.i==-1 ||
					prev.x-(v=getDistance(prev.i, n.i)) <= location[B] ||
					(it=map.find((prev.x-v+n.x)/2)) == map.end() || // always even
					it->second != 2)
			{
				prev=n;
				location[n.i]=n.x;
				stype[n.i]=2;
				add(n.i);
			}
			else
			{
				location[n.i]=prev.x-v;
				stype[n.i]=1;
				add(n.i);
			}
	}

	//for(int i=0;i<N;++i) printf("%d %d\n", stype[i], location[i]);
}

Compilation message

rail.cpp:10:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |            ^~~~
rail.cpp:10:27: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | bool ckmin(auto& a, const auto& b) {return b<a?a=b,1:0;}
      |                           ^~~~
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:68:9: warning: unused variable 'ok' [-Wunused-variable]
   68 |    bool ok=0;
      |         ^~
rail.cpp:37:28: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |  location[B] = first + da[B];
      |                            ^

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 22.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 732 KB Output is correct
2 Correct 98 ms 740 KB Output is correct
3 Correct 92 ms 736 KB Output is correct
4 Correct 89 ms 744 KB Output is correct
5 Correct 83 ms 728 KB Output is correct
6 Correct 84 ms 744 KB Output is correct
7 Correct 99 ms 740 KB Output is correct
8 Correct 93 ms 732 KB Output is correct
9 Correct 85 ms 744 KB Output is correct
10 Correct 85 ms 728 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 728 KB Output is correct
2 Correct 85 ms 732 KB Output is correct
3 Correct 95 ms 736 KB Output is correct
4 Correct 88 ms 708 KB Output is correct
5 Correct 84 ms 736 KB Output is correct
6 Correct 84 ms 732 KB Output is correct
7 Correct 97 ms 736 KB Output is correct
8 Correct 84 ms 744 KB Output is correct
9 Correct 104 ms 728 KB Output is correct
10 Correct 85 ms 728 KB Output is correct
11 Correct 83 ms 744 KB Output is correct
12 Correct 86 ms 672 KB Output is correct
13 Correct 90 ms 792 KB Output is correct
14 Correct 89 ms 728 KB Output is correct
15 Correct 90 ms 760 KB Output is correct
16 Correct 86 ms 744 KB Output is correct
17 Correct 88 ms 732 KB Output is correct
18 Correct 102 ms 708 KB Output is correct
19 Correct 84 ms 748 KB Output is correct
20 Correct 86 ms 728 KB Output is correct