oj.uz

Submission #314461

# Submission time Handle Problem Language Result Execution time Memory
314461 2020-10-20T01:30:00 Z ttnhuy313 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 1000 ms 98440 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef pair <int, int> ii;

const int N = 1e5 + 5;
int n, a[N], trace[N], ans[N];
vector <ii> adj[N];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	// freopen("BOI13_brunhilda.INP", "r", stdin);
	// freopen("BOI13_brunhilda.OUT", "w", stdout);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	int m;
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			for (int k = i; k >= 0; --k) if (k % a[j] == 0) {
				adj[i].push_back({k, j});
				// cerr << i << ' ' << k << endl;
				break;
			}
		}
	}
	queue <int> q; while (!q.empty()) q.pop();
	memset(trace, -1, sizeof trace);
	q.push(m);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (ii d : adj[u]) {
			int v = d.first, val = d.second;
			if (~trace[v]) continue;
			trace[v] = u;
			ans[v] = val;
			q.push(v);
		}
	}
	int cur = 0;
	vector <ii> res; res.clear();
	while (cur != m) {
		res.push_back({trace[cur], cur});
		cur = trace[cur];
	}
	reverse(res.begin(), res.end());
	cout << res.size() << endl;
	for (ii d : res) {
		cout << d.first << " with call " << a[ans[d.second]] << " replaced with " << d.second << endl;
		// cout << a[ans[d.second]] << ' ';
	}

	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3456 KB Output isn't correct
2 Incorrect 17 ms 3968 KB Output isn't correct
3 Incorrect 3 ms 3456 KB Output isn't correct
4 Execution timed out 1092 ms 8492 KB Time limit exceeded
5 Incorrect 3 ms 3584 KB Output isn't correct
6 Incorrect 2 ms 3456 KB Output isn't correct
7 Incorrect 3 ms 3456 KB Output isn't correct
8 Incorrect 2 ms 3456 KB Output isn't correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Incorrect 3 ms 3584 KB Output isn't correct
11 Incorrect 4 ms 3584 KB Output isn't correct
12 Execution timed out 1026 ms 7364 KB Time limit exceeded
13 Execution timed out 1097 ms 13560 KB Time limit exceeded
14 Execution timed out 1095 ms 13300 KB Time limit exceeded
15 Incorrect 10 ms 3712 KB Output isn't correct
16 Incorrect 17 ms 3968 KB Output isn't correct
17 Incorrect 27 ms 4216 KB Output isn't correct
18 Execution timed out 1090 ms 8536 KB Time limit exceeded

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 37036 KB Time limit exceeded
2 Execution timed out 1083 ms 93376 KB Time limit exceeded
3 Execution timed out 1042 ms 80528 KB Time limit exceeded
4 Execution timed out 1037 ms 21500 KB Time limit exceeded
5 Execution timed out 1053 ms 70508 KB Time limit exceeded
6 Execution timed out 1090 ms 16280 KB Time limit exceeded
7 Execution timed out 1090 ms 37236 KB Time limit exceeded
8 Execution timed out 1095 ms 13304 KB Time limit exceeded
9 Execution timed out 1099 ms 83268 KB Time limit exceeded
10 Execution timed out 1063 ms 81796 KB Time limit exceeded
11 Execution timed out 1100 ms 64792 KB Time limit exceeded
12 Execution timed out 1099 ms 19448 KB Time limit exceeded
13 Execution timed out 1096 ms 21624 KB Time limit exceeded
14 Execution timed out 1089 ms 21880 KB Time limit exceeded
15 Execution timed out 1050 ms 64240 KB Time limit exceeded
16 Execution timed out 1097 ms 93588 KB Time limit exceeded
17 Execution timed out 1086 ms 21752 KB Time limit exceeded
18 Execution timed out 1098 ms 98440 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 71348 KB Time limit exceeded
2 Execution timed out 1082 ms 72620 KB Time limit exceeded
3 Execution timed out 1101 ms 71348 KB Time limit exceeded
4 Execution timed out 1098 ms 22904 KB Time limit exceeded
5 Execution timed out 1101 ms 97384 KB Time limit exceeded
6 Execution timed out 1090 ms 31736 KB Time limit exceeded
7 Execution timed out 1093 ms 97460 KB Time limit exceeded
8 Execution timed out 1055 ms 70568 KB Time limit exceeded
9 Execution timed out 1047 ms 69752 KB Time limit exceeded
10 Execution timed out 1095 ms 27896 KB Time limit exceeded
11 Execution timed out 1094 ms 24808 KB Time limit exceeded
12 Execution timed out 1084 ms 27900 KB Time limit exceeded
13 Execution timed out 1080 ms 55336 KB Time limit exceeded
14 Incorrect 4 ms 3584 KB Output isn't correct
15 Execution timed out 1093 ms 25496 KB Time limit exceeded
16 Execution timed out 1086 ms 29552 KB Time limit exceeded
17 Execution timed out 1095 ms 67076 KB Time limit exceeded
18 Execution timed out 1098 ms 72552 KB Time limit exceeded
19 Execution timed out 1047 ms 25772 KB Time limit exceeded
20 Execution timed out 1087 ms 69696 KB Time limit exceeded
21 Incorrect 142 ms 6776 KB Output isn't correct
22 Execution timed out 1084 ms 97064 KB Time limit exceeded
23 Execution timed out 1094 ms 56720 KB Time limit exceeded
24 Execution timed out 1084 ms 15684 KB Time limit exceeded
25 Execution timed out 1052 ms 21276 KB Time limit exceeded
26 Execution timed out 1091 ms 22760 KB Time limit exceeded
27 Execution timed out 1066 ms 95408 KB Time limit exceeded
28 Execution timed out 1091 ms 13172 KB Time limit exceeded
29 Execution timed out 1099 ms 97412 KB Time limit exceeded
30 Execution timed out 1097 ms 81756 KB Time limit exceeded
31 Execution timed out 1093 ms 24696 KB Time limit exceeded
32 Execution timed out 1097 ms 21624 KB Time limit exceeded
33 Execution timed out 1097 ms 16040 KB Time limit exceeded
34 Execution timed out 1098 ms 97524 KB Time limit exceeded
35 Execution timed out 1094 ms 17360 KB Time limit exceeded
36 Execution timed out 1101 ms 92460 KB Time limit exceeded
37 Execution timed out 1092 ms 94296 KB Time limit exceeded
38 Execution timed out 1085 ms 30716 KB Time limit exceeded
39 Execution timed out 1076 ms 19508 KB Time limit exceeded
40 Execution timed out 1047 ms 32488 KB Time limit exceeded
41 Execution timed out 1092 ms 96884 KB Time limit exceeded
42 Execution timed out 1056 ms 21284 KB Time limit exceeded