oj.uz

Submission #793239

# Submission time Handle Problem Language Result Execution time Memory
793239 2023-07-25T16:30:29 Z prvocislo Roller Coaster Railroad (IOI16_railroad) C++17
34 / 100
 90 ms 13556 KB 
#include "railroad.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 1e18 + 5;
void upd(ll& a, ll b) { a = min(a, b); }
long long bruteforce(vector<int> s, vector<int> t) 
{
	int n = s.size();
	// slow
	vector<vector<ll> > dp((1 << n), vector<ll>(n, inf));
	for (int m = 0; m < (1 << n); m++)
	{
		if (!m)
		{
			for (int j = 0; j < n; j++) dp[(1 << j)][j] = 0;
			continue;
		}
		for (int i = 0; i < n; i++) if (m & (1 << i))
		{
			for (int j = 0; j < n; j++) if (!(m & (1 << j)))
			{
				ll di = max(0, t[i] - s[j]);
				upd(dp[m | (1 << j)][j], dp[m][i] + di);
			}
		}
	}
	return *min_element(dp.back().begin(), dp.back().end());
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.first != b.first) return a.first < b.first;
	return a.second > b.second;
}
vector<ll> b(60); // baza
bool add(ll x)
{
	for (ll i = b.size() - 1; i >= 0; i--) if (x & (1ll << i))
	{
		if (b[i]) x ^= b[i];
		else return b[i] = x, true; 
	}
	return false;
}
long long zero(vector<int> s, vector<int> t) // >= 0 budu vystupy, < 0 budu vstupy
{
	b.assign(60, 0);
	int n = s.size();
	vector<pair<int, int> > v;
	v.push_back({ 1, 0 });
	for (int i = 0; i < n; i++) v.push_back({ s[i], -i - 1 }), v.push_back({ t[i], i + 1 });
	sort(v.begin(), v.end(), cmp);

	vector<ll> val(n + 1, 0);
	for (int i = 0; i <= n; i++) val[i] = uniform_int_distribution<ll>(0, (1ll << 60ll) - 1ll)(rng);
	ll pf = 0;
	int in = 0, ou = 0;

	for (pair<int, int> p : v)
	{
		if (p.second >= 0) ou++;
		else in++;
		if (ou < in) return 1;
		pf ^= val[abs(p.second)];
		if (ou == in)
		{
			if (!add(pf)) return 1;
			pf = 0;
		}
	}
	return 0;
}
long long plan_roller_coaster(vector<int> s, vector<int> t)
{
    if (s.size() <= 16) return bruteforce(s, t);
	return zero(s, t);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 300 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 304 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 300 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 308 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 300 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 304 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 300 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 308 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 300 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 34 ms 11008 KB n = 16
30 Correct 35 ms 10964 KB n = 16
31 Correct 34 ms 11068 KB n = 16
32 Correct 35 ms 11068 KB n = 16
33 Correct 34 ms 11092 KB n = 16
34 Correct 41 ms 10964 KB n = 16
35 Correct 40 ms 11076 KB n = 16
36 Correct 16 ms 5076 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 36 ms 11084 KB n = 16
39 Correct 34 ms 10964 KB n = 16
40 Correct 1 ms 340 KB n = 9
41 Correct 35 ms 11220 KB n = 16
42 Correct 34 ms 11092 KB n = 16
43 Correct 36 ms 11092 KB n = 16
44 Correct 1 ms 340 KB n = 9
45 Correct 15 ms 5168 KB n = 15
46 Correct 34 ms 11068 KB n = 16
47 Correct 35 ms 11092 KB n = 16
48 Correct 39 ms 11092 KB n = 16

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 13480 KB n = 199999
2 Correct 84 ms 13540 KB n = 199991
3 Correct 78 ms 13544 KB n = 199993
4 Correct 60 ms 10672 KB n = 152076
5 Correct 46 ms 6404 KB n = 93249
6 Correct 76 ms 12396 KB n = 199910
7 Correct 90 ms 12824 KB n = 199999
8 Correct 75 ms 12464 KB n = 199997
9 Correct 69 ms 11728 KB n = 171294
10 Correct 57 ms 10464 KB n = 140872
11 Correct 76 ms 12452 KB n = 199886
12 Correct 75 ms 12844 KB n = 199996
13 Correct 73 ms 12472 KB n = 200000
14 Correct 74 ms 12752 KB n = 199998
15 Correct 77 ms 12712 KB n = 200000
16 Correct 76 ms 13032 KB n = 199998
17 Correct 82 ms 13476 KB n = 200000
18 Correct 76 ms 12880 KB n = 190000
19 Correct 81 ms 12156 KB n = 177777
20 Correct 39 ms 6844 KB n = 100000
21 Incorrect 79 ms 13556 KB answer is not correct: 1 instead of 0
22 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 2
2 Correct 1 ms 212 KB n = 2
3 Correct 1 ms 300 KB n = 2
4 Correct 1 ms 212 KB n = 2
5 Correct 0 ms 212 KB n = 2
6 Correct 0 ms 304 KB n = 2
7 Correct 0 ms 212 KB n = 3
8 Correct 0 ms 212 KB n = 3
9 Correct 1 ms 212 KB n = 3
10 Correct 1 ms 212 KB n = 8
11 Correct 1 ms 212 KB n = 8
12 Correct 1 ms 212 KB n = 8
13 Correct 1 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 1 ms 212 KB n = 8
16 Correct 1 ms 300 KB n = 8
17 Correct 1 ms 212 KB n = 8
18 Correct 1 ms 212 KB n = 8
19 Correct 0 ms 212 KB n = 3
20 Correct 1 ms 308 KB n = 7
21 Correct 1 ms 212 KB n = 8
22 Correct 1 ms 212 KB n = 8
23 Correct 1 ms 212 KB n = 8
24 Correct 1 ms 212 KB n = 8
25 Correct 0 ms 212 KB n = 8
26 Correct 1 ms 300 KB n = 8
27 Correct 1 ms 212 KB n = 8
28 Correct 1 ms 212 KB n = 8
29 Correct 34 ms 11008 KB n = 16
30 Correct 35 ms 10964 KB n = 16
31 Correct 34 ms 11068 KB n = 16
32 Correct 35 ms 11068 KB n = 16
33 Correct 34 ms 11092 KB n = 16
34 Correct 41 ms 10964 KB n = 16
35 Correct 40 ms 11076 KB n = 16
36 Correct 16 ms 5076 KB n = 15
37 Correct 1 ms 212 KB n = 8
38 Correct 36 ms 11084 KB n = 16
39 Correct 34 ms 10964 KB n = 16
40 Correct 1 ms 340 KB n = 9
41 Correct 35 ms 11220 KB n = 16
42 Correct 34 ms 11092 KB n = 16
43 Correct 36 ms 11092 KB n = 16
44 Correct 1 ms 340 KB n = 9
45 Correct 15 ms 5168 KB n = 15
46 Correct 34 ms 11068 KB n = 16
47 Correct 35 ms 11092 KB n = 16
48 Correct 39 ms 11092 KB n = 16
49 Correct 84 ms 13480 KB n = 199999
50 Correct 84 ms 13540 KB n = 199991
51 Correct 78 ms 13544 KB n = 199993
52 Correct 60 ms 10672 KB n = 152076
53 Correct 46 ms 6404 KB n = 93249
54 Correct 76 ms 12396 KB n = 199910
55 Correct 90 ms 12824 KB n = 199999
56 Correct 75 ms 12464 KB n = 199997
57 Correct 69 ms 11728 KB n = 171294
58 Correct 57 ms 10464 KB n = 140872
59 Correct 76 ms 12452 KB n = 199886
60 Correct 75 ms 12844 KB n = 199996
61 Correct 73 ms 12472 KB n = 200000
62 Correct 74 ms 12752 KB n = 199998
63 Correct 77 ms 12712 KB n = 200000
64 Correct 76 ms 13032 KB n = 199998
65 Correct 82 ms 13476 KB n = 200000
66 Correct 76 ms 12880 KB n = 190000
67 Correct 81 ms 12156 KB n = 177777
68 Correct 39 ms 6844 KB n = 100000
69 Incorrect 79 ms 13556 KB answer is not correct: 1 instead of 0
70 Halted 0 ms 0 KB -