답안 #369838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369838	2021-02-22T15:18:38 Z	mario05092929	Lamps (JOI19_lamps)	C++11	100 / 100	213 ms	161076 KB

lamp

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e16;
const long long mod = 998244353;
const long long hashmod = 100003;
const int MAXN = 100000;
const int MAXM = 1000000;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,d[1000005][4][2];
// d[i][j][k] : 어떤 st부터 i번 문자까지 k(0 : B와같이, 1 : B역순으로)상태로 만들었고 그 전에 사용한 연산이 j(0 : 아무것도 안함, 1 : 0로 만들기, 2 : 1로 만들기)일때 최소 횟수 
char a[1000005],b[1000005];

int go(int x,int op,int fl) {
	if(x == n+1) return 0;
	if(d[x][op][fl] != -1) return d[x][op][fl];
	int &ret = d[x][op][fl]; ret = INF;
	int na = a[x]-'0', nb = b[x]-'0';
	for(int i = 0;i < 3;i++) {
		for(int j = 0;j < 2;j++) {
			int us = 0,nx = na;
			if(i == 1) nx = 0;
			if(i == 2) nx = 1;
			if(j) nx ^= 1;
			if(op != i&&i) us++;
			if(fl != j&&j) us++;
			if(nx == nb) ret = min(ret,go(x+1,i,j)+us);
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> a+1 >> b+1;
	memset(d,-1,sizeof(d));
	cout << go(1,3,0);
}

Compilation message

lamp.cpp:6: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    6 | #pragma gcc optimize("O3")
      | 
lamp.cpp:7: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    7 | #pragma gcc optimize("Ofast")
      | 
lamp.cpp:8: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    8 | #pragma gcc optimize("unroll-loops")
      | 
lamp.cpp: In function 'int main()':
lamp.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  cin >> n >> a+1 >> b+1;
      |              ~^~
lamp.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  cin >> n >> a+1 >> b+1;
      |                     ~^~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31596 KB	Output is correct
2	Correct	16 ms	31596 KB	Output is correct
3	Correct	17 ms	31596 KB	Output is correct
4	Correct	17 ms	31596 KB	Output is correct
5	Correct	17 ms	31596 KB	Output is correct
6	Correct	17 ms	31596 KB	Output is correct
7	Correct	16 ms	31596 KB	Output is correct
8	Correct	17 ms	31596 KB	Output is correct
9	Correct	17 ms	31596 KB	Output is correct
10	Correct	17 ms	31596 KB	Output is correct
11	Correct	17 ms	31596 KB	Output is correct
12	Correct	16 ms	31596 KB	Output is correct
13	Correct	18 ms	31596 KB	Output is correct
14	Correct	17 ms	31596 KB	Output is correct
15	Correct	17 ms	31596 KB	Output is correct
16	Correct	17 ms	31596 KB	Output is correct
17	Correct	18 ms	31724 KB	Output is correct
18	Correct	17 ms	31596 KB	Output is correct
19	Correct	17 ms	31596 KB	Output is correct
20	Correct	17 ms	31596 KB	Output is correct
21	Correct	17 ms	31596 KB	Output is correct
22	Correct	17 ms	31596 KB	Output is correct
23	Correct	17 ms	31596 KB	Output is correct
24	Correct	17 ms	31744 KB	Output is correct
25	Correct	17 ms	31596 KB	Output is correct
26	Correct	19 ms	31596 KB	Output is correct
27	Correct	19 ms	31596 KB	Output is correct
28	Correct	18 ms	31596 KB	Output is correct
29	Correct	17 ms	31596 KB	Output is correct
30	Correct	17 ms	31596 KB	Output is correct
31	Correct	17 ms	31596 KB	Output is correct
32	Correct	17 ms	31596 KB	Output is correct
33	Correct	17 ms	31596 KB	Output is correct
34	Correct	17 ms	31596 KB	Output is correct

Subtask #2
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31596 KB	Output is correct
2	Correct	16 ms	31596 KB	Output is correct
3	Correct	17 ms	31596 KB	Output is correct
4	Correct	17 ms	31596 KB	Output is correct
5	Correct	17 ms	31596 KB	Output is correct
6	Correct	17 ms	31596 KB	Output is correct
7	Correct	16 ms	31596 KB	Output is correct
8	Correct	17 ms	31596 KB	Output is correct
9	Correct	17 ms	31596 KB	Output is correct
10	Correct	17 ms	31596 KB	Output is correct
11	Correct	17 ms	31596 KB	Output is correct
12	Correct	16 ms	31596 KB	Output is correct
13	Correct	18 ms	31596 KB	Output is correct
14	Correct	17 ms	31596 KB	Output is correct
15	Correct	17 ms	31596 KB	Output is correct
16	Correct	17 ms	31596 KB	Output is correct
17	Correct	18 ms	31724 KB	Output is correct
18	Correct	17 ms	31596 KB	Output is correct
19	Correct	17 ms	31596 KB	Output is correct
20	Correct	17 ms	31596 KB	Output is correct
21	Correct	17 ms	31596 KB	Output is correct
22	Correct	17 ms	31596 KB	Output is correct
23	Correct	17 ms	31596 KB	Output is correct
24	Correct	17 ms	31744 KB	Output is correct
25	Correct	17 ms	31596 KB	Output is correct
26	Correct	19 ms	31596 KB	Output is correct
27	Correct	19 ms	31596 KB	Output is correct
28	Correct	18 ms	31596 KB	Output is correct
29	Correct	17 ms	31596 KB	Output is correct
30	Correct	17 ms	31596 KB	Output is correct
31	Correct	17 ms	31596 KB	Output is correct
32	Correct	17 ms	31596 KB	Output is correct
33	Correct	17 ms	31596 KB	Output is correct
34	Correct	17 ms	31596 KB	Output is correct
35	Correct	18 ms	31852 KB	Output is correct
36	Correct	16 ms	31852 KB	Output is correct
37	Correct	17 ms	31852 KB	Output is correct
38	Correct	18 ms	31852 KB	Output is correct
39	Correct	17 ms	31852 KB	Output is correct
40	Correct	17 ms	31852 KB	Output is correct
41	Correct	17 ms	31852 KB	Output is correct
42	Correct	17 ms	31852 KB	Output is correct
43	Correct	18 ms	31852 KB	Output is correct
44	Correct	17 ms	31980 KB	Output is correct
45	Correct	17 ms	31872 KB	Output is correct
46	Correct	17 ms	31852 KB	Output is correct
47	Correct	18 ms	31852 KB	Output is correct
48	Correct	17 ms	31852 KB	Output is correct
49	Correct	17 ms	31852 KB	Output is correct
50	Correct	18 ms	31852 KB	Output is correct
51	Correct	17 ms	31852 KB	Output is correct
52	Correct	17 ms	31852 KB	Output is correct
53	Correct	17 ms	31852 KB	Output is correct
54	Correct	18 ms	31852 KB	Output is correct
55	Correct	17 ms	31852 KB	Output is correct
56	Correct	18 ms	31852 KB	Output is correct
57	Correct	18 ms	31852 KB	Output is correct
58	Correct	18 ms	31852 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31596 KB	Output is correct
2	Correct	16 ms	31596 KB	Output is correct
3	Correct	16 ms	31596 KB	Output is correct
4	Correct	17 ms	31596 KB	Output is correct
5	Correct	17 ms	31596 KB	Output is correct
6	Correct	17 ms	31596 KB	Output is correct
7	Correct	187 ms	160932 KB	Output is correct
8	Correct	188 ms	160856 KB	Output is correct
9	Correct	188 ms	160876 KB	Output is correct
10	Correct	189 ms	161004 KB	Output is correct
11	Correct	188 ms	160896 KB	Output is correct
12	Correct	190 ms	160876 KB	Output is correct
13	Correct	190 ms	160876 KB	Output is correct
14	Correct	204 ms	160876 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31596 KB	Output is correct
2	Correct	16 ms	31596 KB	Output is correct
3	Correct	17 ms	31596 KB	Output is correct
4	Correct	17 ms	31596 KB	Output is correct
5	Correct	17 ms	31596 KB	Output is correct
6	Correct	17 ms	31596 KB	Output is correct
7	Correct	16 ms	31596 KB	Output is correct
8	Correct	17 ms	31596 KB	Output is correct
9	Correct	17 ms	31596 KB	Output is correct
10	Correct	17 ms	31596 KB	Output is correct
11	Correct	17 ms	31596 KB	Output is correct
12	Correct	16 ms	31596 KB	Output is correct
13	Correct	18 ms	31596 KB	Output is correct
14	Correct	17 ms	31596 KB	Output is correct
15	Correct	17 ms	31596 KB	Output is correct
16	Correct	17 ms	31596 KB	Output is correct
17	Correct	18 ms	31724 KB	Output is correct
18	Correct	17 ms	31596 KB	Output is correct
19	Correct	17 ms	31596 KB	Output is correct
20	Correct	17 ms	31596 KB	Output is correct
21	Correct	17 ms	31596 KB	Output is correct
22	Correct	17 ms	31596 KB	Output is correct
23	Correct	17 ms	31596 KB	Output is correct
24	Correct	17 ms	31744 KB	Output is correct
25	Correct	17 ms	31596 KB	Output is correct
26	Correct	19 ms	31596 KB	Output is correct
27	Correct	19 ms	31596 KB	Output is correct
28	Correct	18 ms	31596 KB	Output is correct
29	Correct	17 ms	31596 KB	Output is correct
30	Correct	17 ms	31596 KB	Output is correct
31	Correct	17 ms	31596 KB	Output is correct
32	Correct	17 ms	31596 KB	Output is correct
33	Correct	17 ms	31596 KB	Output is correct
34	Correct	17 ms	31596 KB	Output is correct
35	Correct	18 ms	31852 KB	Output is correct
36	Correct	16 ms	31852 KB	Output is correct
37	Correct	17 ms	31852 KB	Output is correct
38	Correct	18 ms	31852 KB	Output is correct
39	Correct	17 ms	31852 KB	Output is correct
40	Correct	17 ms	31852 KB	Output is correct
41	Correct	17 ms	31852 KB	Output is correct
42	Correct	17 ms	31852 KB	Output is correct
43	Correct	18 ms	31852 KB	Output is correct
44	Correct	17 ms	31980 KB	Output is correct
45	Correct	17 ms	31872 KB	Output is correct
46	Correct	17 ms	31852 KB	Output is correct
47	Correct	18 ms	31852 KB	Output is correct
48	Correct	17 ms	31852 KB	Output is correct
49	Correct	17 ms	31852 KB	Output is correct
50	Correct	18 ms	31852 KB	Output is correct
51	Correct	17 ms	31852 KB	Output is correct
52	Correct	17 ms	31852 KB	Output is correct
53	Correct	17 ms	31852 KB	Output is correct
54	Correct	18 ms	31852 KB	Output is correct
55	Correct	17 ms	31852 KB	Output is correct
56	Correct	18 ms	31852 KB	Output is correct
57	Correct	18 ms	31852 KB	Output is correct
58	Correct	18 ms	31852 KB	Output is correct
59	Correct	17 ms	31596 KB	Output is correct
60	Correct	16 ms	31596 KB	Output is correct
61	Correct	16 ms	31596 KB	Output is correct
62	Correct	17 ms	31596 KB	Output is correct
63	Correct	17 ms	31596 KB	Output is correct
64	Correct	17 ms	31596 KB	Output is correct
65	Correct	187 ms	160932 KB	Output is correct
66	Correct	188 ms	160856 KB	Output is correct
67	Correct	188 ms	160876 KB	Output is correct
68	Correct	189 ms	161004 KB	Output is correct
69	Correct	188 ms	160896 KB	Output is correct
70	Correct	190 ms	160876 KB	Output is correct
71	Correct	190 ms	160876 KB	Output is correct
72	Correct	204 ms	160876 KB	Output is correct
73	Correct	186 ms	160876 KB	Output is correct
74	Correct	197 ms	160904 KB	Output is correct
75	Correct	189 ms	160876 KB	Output is correct
76	Correct	185 ms	160876 KB	Output is correct
77	Correct	200 ms	160748 KB	Output is correct
78	Correct	192 ms	160876 KB	Output is correct
79	Correct	186 ms	160876 KB	Output is correct
80	Correct	184 ms	160876 KB	Output is correct
81	Correct	186 ms	160748 KB	Output is correct
82	Correct	187 ms	160876 KB	Output is correct
83	Correct	201 ms	160876 KB	Output is correct
84	Correct	196 ms	160876 KB	Output is correct
85	Correct	196 ms	160876 KB	Output is correct
86	Correct	202 ms	160988 KB	Output is correct
87	Correct	204 ms	161040 KB	Output is correct
88	Correct	199 ms	160876 KB	Output is correct
89	Correct	213 ms	161004 KB	Output is correct
90	Correct	203 ms	160876 KB	Output is correct
91	Correct	201 ms	160876 KB	Output is correct
92	Correct	202 ms	161076 KB	Output is correct
93	Correct	206 ms	160876 KB	Output is correct
94	Correct	205 ms	160876 KB	Output is correct
95	Correct	206 ms	160876 KB	Output is correct
96	Correct	203 ms	160876 KB	Output is correct
97	Correct	207 ms	160876 KB	Output is correct
98	Correct	202 ms	160876 KB	Output is correct
99	Correct	202 ms	160876 KB	Output is correct
100	Correct	203 ms	160876 KB	Output is correct
101	Correct	200 ms	160876 KB	Output is correct
102	Correct	202 ms	160876 KB	Output is correct

답안 #369838

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 41.0 / 41.0

Subtask #3 4.0 / 4.0

Subtask #4 49.0 / 49.0

Subtask #1
6.0 / 6.0

Subtask #2
41.0 / 41.0

Subtask #3
4.0 / 4.0

Subtask #4
49.0 / 49.0