oj.uz

답안 #553894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553894 2022-04-27T09:04:29 Z pavement Lamps (JOI19_lamps) C++17
0 / 100
 1000 ms 2688 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, dp[2][365];
bool A[1000005], B[1000005];
char C;

vector<ii> vec;

bool apply(bool x, int b) {
	int bm = vec[b].second;
	for (int k = 0; k < vec[b].first; k++) {
		if (bm % 3 == 0) x = 0;
		else if (bm % 3 == 1) x = 1;
		else x ^= 1;
		bm /= 3;
	}
	return x;
}

int cst(int a, int b) {
	int lcp = 0, bma = vec[a].second, bmb = vec[b].second;
	for (int i = 0; i < min(vec[a].first, vec[b].first); i++) {
		if (bma % 3 == bmb % 3) lcp = i + 1;
		else break;
		bma /= 3;
		bmb /= 3;
	}
	return vec[b].first - lcp;
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0, p = 1; i <= 5; i++) {
		for (int j = 0; j < p; j++) vec.eb(i, j);
		p *= 3;
	}
	for (int i = 1; i <= N; i++) {
		cin >> C;
		A[i] = C == '1';
	}
	for (int i = 1; i <= N; i++) {
		cin >> C;
		B[i] = C == '1';
	}
	for (int i = N; i >= 1; i--)
		for (int b = 0; b < 365; b++) {
			dp[i & 1][b] = INT_MAX;
			for (int nb = 0; nb < 365; nb++)
				if (apply(A[i], nb) == B[i]) dp[i & 1][b] = min(dp[i & 1][b], dp[i & 1 ^ 1][nb] + cst(b, nb));
		}
	cout << dp[1][0] << '\n';
}

Compilation message

lamp.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~
lamp.cpp: In function 'int main()':
lamp.cpp:77:72: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   77 |     if (apply(A[i], nb) == B[i]) dp[i & 1][b] = min(dp[i & 1][b], dp[i & 1 ^ 1][nb] + cst(b, nb));
      |                                                                      ~~^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 43 ms 340 KB Output is correct
9 Correct 44 ms 340 KB Output is correct
10 Correct 41 ms 340 KB Output is correct
11 Correct 42 ms 448 KB Output is correct
12 Correct 43 ms 340 KB Output is correct
13 Correct 40 ms 340 KB Output is correct
14 Correct 43 ms 340 KB Output is correct
15 Correct 42 ms 332 KB Output is correct
16 Correct 45 ms 340 KB Output is correct
17 Correct 40 ms 340 KB Output is correct
18 Correct 43 ms 340 KB Output is correct
19 Correct 41 ms 340 KB Output is correct
20 Correct 43 ms 340 KB Output is correct
21 Correct 40 ms 340 KB Output is correct
22 Correct 43 ms 340 KB Output is correct
23 Correct 42 ms 340 KB Output is correct
24 Correct 46 ms 332 KB Output is correct
25 Correct 42 ms 340 KB Output is correct
26 Incorrect 44 ms 332 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 43 ms 340 KB Output is correct
9 Correct 44 ms 340 KB Output is correct
10 Correct 41 ms 340 KB Output is correct
11 Correct 42 ms 448 KB Output is correct
12 Correct 43 ms 340 KB Output is correct
13 Correct 40 ms 340 KB Output is correct
14 Correct 43 ms 340 KB Output is correct
15 Correct 42 ms 332 KB Output is correct
16 Correct 45 ms 340 KB Output is correct
17 Correct 40 ms 340 KB Output is correct
18 Correct 43 ms 340 KB Output is correct
19 Correct 41 ms 340 KB Output is correct
20 Correct 43 ms 340 KB Output is correct
21 Correct 40 ms 340 KB Output is correct
22 Correct 43 ms 340 KB Output is correct
23 Correct 42 ms 340 KB Output is correct
24 Correct 46 ms 332 KB Output is correct
25 Correct 42 ms 340 KB Output is correct
26 Incorrect 44 ms 332 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 328 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Execution timed out 1088 ms 2688 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 43 ms 340 KB Output is correct
9 Correct 44 ms 340 KB Output is correct
10 Correct 41 ms 340 KB Output is correct
11 Correct 42 ms 448 KB Output is correct
12 Correct 43 ms 340 KB Output is correct
13 Correct 40 ms 340 KB Output is correct
14 Correct 43 ms 340 KB Output is correct
15 Correct 42 ms 332 KB Output is correct
16 Correct 45 ms 340 KB Output is correct
17 Correct 40 ms 340 KB Output is correct
18 Correct 43 ms 340 KB Output is correct
19 Correct 41 ms 340 KB Output is correct
20 Correct 43 ms 340 KB Output is correct
21 Correct 40 ms 340 KB Output is correct
22 Correct 43 ms 340 KB Output is correct
23 Correct 42 ms 340 KB Output is correct
24 Correct 46 ms 332 KB Output is correct
25 Correct 42 ms 340 KB Output is correct
26 Incorrect 44 ms 332 KB Output isn't correct
27 Halted 0 ms 0 KB -