oj.uz

Submission #314462

# Submission time Handle Problem Language Result Execution time Memory
314462 2020-10-20T01:30:44 Z ttnhuy313 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 1000 ms 97820 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;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:52:10: warning: variable 'd' set but not used [-Wunused-but-set-variable]
   52 |  for (ii d : res) {
      |          ^

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 1089 ms 8464 KB Time limit exceeded
5 Incorrect 3 ms 3456 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 4 ms 3456 KB Output isn't correct
10 Incorrect 3 ms 3584 KB Output isn't correct
11 Incorrect 3 ms 3584 KB Output isn't correct
12 Execution timed out 1046 ms 6948 KB Time limit exceeded
13 Execution timed out 1095 ms 13304 KB Time limit exceeded
14 Execution timed out 1090 ms 13228 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 4224 KB Output isn't correct
18 Execution timed out 1094 ms 8452 KB Time limit exceeded

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 35652 KB Time limit exceeded
2 Execution timed out 1049 ms 89976 KB Time limit exceeded
3 Execution timed out 1094 ms 81096 KB Time limit exceeded
4 Execution timed out 1088 ms 21848 KB Time limit exceeded
5 Execution timed out 1095 ms 70024 KB Time limit exceeded
6 Execution timed out 1092 ms 16180 KB Time limit exceeded
7 Execution timed out 1085 ms 36428 KB Time limit exceeded
8 Execution timed out 1083 ms 12892 KB Time limit exceeded
9 Execution timed out 1076 ms 81380 KB Time limit exceeded
10 Execution timed out 1095 ms 81188 KB Time limit exceeded
11 Execution timed out 1099 ms 63864 KB Time limit exceeded
12 Execution timed out 1079 ms 18988 KB Time limit exceeded
13 Execution timed out 1054 ms 21160 KB Time limit exceeded
14 Execution timed out 1047 ms 21212 KB Time limit exceeded
15 Execution timed out 1086 ms 65340 KB Time limit exceeded
16 Execution timed out 1064 ms 91012 KB Time limit exceeded
17 Execution timed out 1059 ms 21248 KB Time limit exceeded
18 Execution timed out 1095 ms 95968 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 67672 KB Time limit exceeded
2 Execution timed out 1050 ms 70448 KB Time limit exceeded
3 Execution timed out 1027 ms 67660 KB Time limit exceeded
4 Execution timed out 1089 ms 22348 KB Time limit exceeded
5 Execution timed out 1051 ms 92408 KB Time limit exceeded
6 Execution timed out 1044 ms 30588 KB Time limit exceeded
7 Execution timed out 1096 ms 96012 KB Time limit exceeded
8 Execution timed out 1094 ms 70844 KB Time limit exceeded
9 Execution timed out 1101 ms 70912 KB Time limit exceeded
10 Execution timed out 1098 ms 28024 KB Time limit exceeded
11 Execution timed out 1096 ms 24776 KB Time limit exceeded
12 Execution timed out 1088 ms 27896 KB Time limit exceeded
13 Execution timed out 1078 ms 55892 KB Time limit exceeded
14 Incorrect 4 ms 3584 KB Output isn't correct
15 Execution timed out 1085 ms 26576 KB Time limit exceeded
16 Execution timed out 1052 ms 29048 KB Time limit exceeded
17 Execution timed out 1052 ms 66192 KB Time limit exceeded
18 Execution timed out 1061 ms 71128 KB Time limit exceeded
19 Execution timed out 1047 ms 25848 KB Time limit exceeded
20 Execution timed out 1101 ms 70952 KB Time limit exceeded
21 Incorrect 143 ms 6904 KB Output isn't correct
22 Execution timed out 1098 ms 97820 KB Time limit exceeded
23 Execution timed out 1092 ms 56392 KB Time limit exceeded
24 Execution timed out 1093 ms 16080 KB Time limit exceeded
25 Execution timed out 1085 ms 21604 KB Time limit exceeded
26 Execution timed out 1054 ms 22208 KB Time limit exceeded
27 Execution timed out 1097 ms 96488 KB Time limit exceeded
28 Execution timed out 1095 ms 13036 KB Time limit exceeded
29 Execution timed out 1097 ms 96388 KB Time limit exceeded
30 Execution timed out 1099 ms 82456 KB Time limit exceeded
31 Execution timed out 1096 ms 24696 KB Time limit exceeded
32 Execution timed out 1099 ms 21624 KB Time limit exceeded
33 Execution timed out 1093 ms 16248 KB Time limit exceeded
34 Execution timed out 1104 ms 97556 KB Time limit exceeded
35 Execution timed out 1097 ms 17272 KB Time limit exceeded
36 Execution timed out 1095 ms 91668 KB Time limit exceeded
37 Execution timed out 1099 ms 96472 KB Time limit exceeded
38 Execution timed out 1090 ms 31224 KB Time limit exceeded
39 Execution timed out 1096 ms 19460 KB Time limit exceeded
40 Execution timed out 1085 ms 33104 KB Time limit exceeded
41 Execution timed out 1100 ms 96588 KB Time limit exceeded
42 Execution timed out 1087 ms 21880 KB Time limit exceeded