Submission #212806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
212806	2020-03-24T10:43:11 Z	GioChkhaidze	Building 4 (JOI20_building4)	C++14	100 / 100	398 ms	36204 KB

building4

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+6;
int n,a[N],b[N],dp[N][2][2];
main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	scanf("%d",&n); n*=2;
	for (int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for (int i=1; i<=n; i++)
		scanf("%d",&b[i]);
	
	for (int i=0; i<=n; i++) {
		dp[i][0][0]=1e9;
		dp[i][0][1]=-1e9;
		dp[i][1][0]=1e9;
		dp[i][1][1]=-1e9;
	}	

	dp[0][0][0]=0;
	dp[0][0][1]=0;
	dp[0][1][0]=0;
	dp[0][1][1]=0;
	
	for (int i=1; i<=n; i++) {
		if (a[i-1]<=a[i]) {
			dp[i][0][0]=min(dp[i][0][0],dp[i-1][0][0]+1);
			dp[i][0][1]=max(dp[i][0][1],dp[i-1][0][1]+1);
		}
		
		if (a[i-1]<=b[i]) {
			dp[i][1][0]=min(dp[i][1][0],dp[i-1][0][0]-1);
			dp[i][1][1]=max(dp[i][1][1],dp[i-1][0][1]-1);
		}
		
		if (b[i-1]<=a[i]) {
			dp[i][0][0]=min(dp[i][0][0],dp[i-1][1][0]+1);
			dp[i][0][1]=max(dp[i][0][1],dp[i-1][1][1]+1);
		}
		
		if (b[i-1]<=b[i]) {
			dp[i][1][0]=min(dp[i][1][0],dp[i-1][1][0]-1);
			dp[i][1][1]=max(dp[i][1][1],dp[i-1][1][1]-1);
		}
	}
	
	int f=0,l=1e9;
	string ans="";
	for (int i=n; i>=1; i--) {	
		if (dp[i][0][0]<=f && f<=dp[i][0][1] && a[i]<=l) {
			--f,l=a[i];
			ans+='A';
		}
			else
		if (dp[i][1][0]<=f && f<=dp[i][1][1] && b[i]<=l) {
			++f,l=b[i];
			ans+='B';
		}
			else {
			cout<<-1<<endl;
			return 0;
		}
	}
	
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;	
}

Compilation message

building4.cpp:5:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
building4.cpp: In function 'int main()':
building4.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); n*=2;
  ~~~~~^~~~~~~~~
building4.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
building4.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	504 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	6 ms	504 KB	Output is correct
12	Correct	6 ms	640 KB	Output is correct
13	Correct	6 ms	512 KB	Output is correct
14	Correct	6 ms	512 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	6 ms	512 KB	Output is correct
19	Correct	6 ms	512 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	5 ms	512 KB	Output is correct
23	Correct	5 ms	512 KB	Output is correct
24	Correct	6 ms	512 KB	Output is correct
25	Correct	5 ms	512 KB	Output is correct
26	Correct	6 ms	512 KB	Output is correct
27	Correct	6 ms	512 KB	Output is correct
28	Correct	5 ms	512 KB	Output is correct
29	Correct	6 ms	512 KB	Output is correct
30	Correct	6 ms	512 KB	Output is correct
31	Correct	6 ms	512 KB	Output is correct
32	Correct	5 ms	512 KB	Output is correct
33	Correct	6 ms	512 KB	Output is correct

Subtask #2
89.0 / 89.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	504 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	6 ms	504 KB	Output is correct
12	Correct	6 ms	640 KB	Output is correct
13	Correct	6 ms	512 KB	Output is correct
14	Correct	6 ms	512 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	6 ms	512 KB	Output is correct
19	Correct	6 ms	512 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	5 ms	512 KB	Output is correct
23	Correct	5 ms	512 KB	Output is correct
24	Correct	6 ms	512 KB	Output is correct
25	Correct	5 ms	512 KB	Output is correct
26	Correct	6 ms	512 KB	Output is correct
27	Correct	6 ms	512 KB	Output is correct
28	Correct	5 ms	512 KB	Output is correct
29	Correct	6 ms	512 KB	Output is correct
30	Correct	6 ms	512 KB	Output is correct
31	Correct	6 ms	512 KB	Output is correct
32	Correct	5 ms	512 KB	Output is correct
33	Correct	6 ms	512 KB	Output is correct
34	Correct	382 ms	24952 KB	Output is correct
35	Correct	360 ms	25648 KB	Output is correct
36	Correct	344 ms	25520 KB	Output is correct
37	Correct	348 ms	25648 KB	Output is correct
38	Correct	307 ms	25648 KB	Output is correct
39	Correct	306 ms	27312 KB	Output is correct
40	Correct	329 ms	27372 KB	Output is correct
41	Correct	288 ms	26672 KB	Output is correct
42	Correct	379 ms	26672 KB	Output is correct
43	Correct	379 ms	27372 KB	Output is correct
44	Correct	398 ms	27372 KB	Output is correct
45	Correct	377 ms	27500 KB	Output is correct
46	Correct	351 ms	27500 KB	Output is correct
47	Correct	345 ms	27500 KB	Output is correct
48	Correct	329 ms	27500 KB	Output is correct
49	Correct	325 ms	27372 KB	Output is correct
50	Correct	365 ms	27372 KB	Output is correct
51	Correct	369 ms	27312 KB	Output is correct
52	Correct	267 ms	33516 KB	Output is correct
53	Correct	271 ms	33644 KB	Output is correct
54	Correct	245 ms	33644 KB	Output is correct
55	Correct	245 ms	33004 KB	Output is correct
56	Correct	353 ms	27380 KB	Output is correct
57	Correct	289 ms	36076 KB	Output is correct
58	Correct	282 ms	36204 KB	Output is correct
59	Correct	276 ms	36204 KB	Output is correct
60	Correct	272 ms	34992 KB	Output is correct
61	Correct	297 ms	35820 KB	Output is correct
62	Correct	283 ms	35052 KB	Output is correct
63	Correct	295 ms	35436 KB	Output is correct
64	Correct	283 ms	34480 KB	Output is correct
65	Correct	295 ms	34668 KB	Output is correct

Submission #212806

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 89.0 / 89.0

Subtask #1
11.0 / 11.0

Subtask #2
89.0 / 89.0