oj.uz

Submission #283589

# Submission time Handle Problem Language Result Execution time Memory
283589 2020-08-26T02:16:18 Z arnold518 World of Tank (innopolis2018_final_E) C++14
30 / 100
 976 ms 664 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;
const int MAXM = 1e6;

int N, M1, M2, T;
int A[MAXM+10], B[MAXM+10];
int S[10][MAXN+10];

int bef[10][MAXN+10];

vector<int> solve(pii s, pii e)
{
	memset(bef, -1, sizeof(bef));
	queue<pii> Q;
	Q.push(s); bef[s.first][s.second]=0;
	while(!Q.empty())
	{
		pii now=Q.front(); Q.pop();
		if(!S[now.first][now.second+1] && bef[now.first][now.second+1]==-1)
		{
			bef[now.first][now.second+1]=1;
			Q.push({now.first, now.second+1});
		}
		if(!S[3-now.first][now.second] && bef[3-now.first][now.second]==-1)
		{
			bef[3-now.first][now.second]=2;
			Q.push({3-now.first, now.second});
		}
	}

	pii p;
	if(e.first!=0)
	{
		if(bef[e.first][e.second]==-1) return vector<int>(1, -1);
		p=e;
	}
	else
	{
		if(bef[1][e.second]!=-1) p={1, e.second};
		else if(bef[2][e.second]!=-1) p={2, e.second};
		else return vector<int>(1, -1);
	}

	vector<int> ans;
	while(1)
	{
		if(p==s) break;
		if(bef[p.first][p.second]==1) p.second--;
		else p.first=3-p.first, ans.push_back(p.second);
	}
	
	reverse(ans.begin(), ans.end());
	return ans;
}

int main()
{
	scanf("%d%d%d%d", &N, &M1, &M2, &T);
	for(int i=1; i<=M1; i++) scanf("%d", &A[i]), S[1][A[i]]=1;
	for(int i=1; i<=M2; i++) scanf("%d", &B[i]), S[2][B[i]]=1;

	vector<int> NO; NO.push_back(-1);
	vector<int> V1, V2;
	V1=solve({1, 0}, {0, N+1});
	if(V1!=NO)
	{
		printf("Yes\n");
		printf("%d\n", V1.size());
		for(auto it : V1) printf("%d ", it); printf("\n");
		printf("0\n");
		return 0;
	}
	for(int i=1; i<=M1; i++)
	{
		if(A[i]<T) continue;
		S[1][A[i]]=0;

		V1=solve({1, 0}, {1, A[i]-1});
		V2=solve({1, A[i]}, {0, N+1});

		if(V1!=NO && V2!=NO)
		{
			printf("Yes\n");
			printf("%d\n", V1.size()+V2.size());
			for(auto it : V1) printf("%d ", it); printf("\n");
			for(auto it : V2) printf("%d ", it); printf("\n");
			printf("1\n");
			printf("%d 1\n", A[i]-1);
			return 0;
		}

		S[1][A[i]]=1;
	}
	for(int i=1; i<=M2; i++)
	{
		if(B[i]<T) continue;
		S[2][B[i]]=0;

		V1=solve({1, 0}, {2, B[i]-1});
		V2=solve({2, B[i]}, {0, N+1});

		if(V1!=NO && V2!=NO)
		{
			printf("Yes\n");
			printf("%d\n", V1.size()+V2.size());
			for(auto it : V1) printf("%d ", it); printf("\n");
			for(auto it : V2) printf("%d ", it); printf("\n");
			printf("1\n");
			printf("%d 2\n", B[i]-1);
			return 0;
		}
		S[2][B[i]]=1;
	}
	printf("No\n");
}

Compilation message

E.cpp: In function 'int main()':
E.cpp:74:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   74 |   printf("%d\n", V1.size());
      |           ~^     ~~~~~~~~~
      |            |            |
      |            int          std::vector<int>::size_type {aka long unsigned int}
      |           %ld
E.cpp:75:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   75 |   for(auto it : V1) printf("%d ", it); printf("\n");
      |   ^~~
E.cpp:75:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |   for(auto it : V1) printf("%d ", it); printf("\n");
      |                                        ^~~~~~
E.cpp:90:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   90 |    printf("%d\n", V1.size()+V2.size());
      |            ~^     ~~~~~~~~~~~~~~~~~~~
      |             |              |
      |             int            std::vector<int>::size_type {aka long unsigned int}
      |            %ld
E.cpp:91:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   91 |    for(auto it : V1) printf("%d ", it); printf("\n");
      |    ^~~
E.cpp:91:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |    for(auto it : V1) printf("%d ", it); printf("\n");
      |                                         ^~~~~~
E.cpp:92:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |    for(auto it : V2) printf("%d ", it); printf("\n");
      |    ^~~
E.cpp:92:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |    for(auto it : V2) printf("%d ", it); printf("\n");
      |                                         ^~~~~~
E.cpp:111:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  111 |    printf("%d\n", V1.size()+V2.size());
      |            ~^     ~~~~~~~~~~~~~~~~~~~
      |             |              |
      |             int            std::vector<int>::size_type {aka long unsigned int}
      |            %ld
E.cpp:112:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  112 |    for(auto it : V1) printf("%d ", it); printf("\n");
      |    ^~~
E.cpp:112:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  112 |    for(auto it : V1) printf("%d ", it); printf("\n");
      |                                         ^~~~~~
E.cpp:113:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  113 |    for(auto it : V2) printf("%d ", it); printf("\n");
      |    ^~~
E.cpp:113:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  113 |    for(auto it : V2) printf("%d ", it); printf("\n");
      |                                         ^~~~~~
E.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d%d%d%d", &N, &M1, &M2, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.cpp:65:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  for(int i=1; i<=M1; i++) scanf("%d", &A[i]), S[1][A[i]]=1;
      |                           ~~~~~^~~~~~~~~~~~~
E.cpp:66:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  for(int i=1; i<=M2; i++) scanf("%d", &B[i]), S[2][B[i]]=1;
      |                           ~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 1 ms 640 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 1 ms 640 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 67 ms 640 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 976 ms 660 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 340 ms 640 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 390 ms 544 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 435 ms 656 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 622 ms 652 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 405 ms 648 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 931 ms 664 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 894 ms 640 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 544 KB [No solution found] n = 20, m1 = 12, m2 = 9, t = 3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 1 ms 640 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 67 ms 640 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 976 ms 660 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 340 ms 640 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 390 ms 544 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 435 ms 656 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 622 ms 652 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 405 ms 648 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 931 ms 664 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 894 ms 640 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Incorrect 9 ms 512 KB [No solution found] n = 500, m1 = 197, m2 = 53, t = 2
25 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB [OK, Yes] n = 20, m1 = 20, m2 = 0, t = 20
2 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 509, m2 = 491, t = 5000
3 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 2 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1006, m2 = 995, t = 5000
10 Correct 1 ms 512 KB [OK, No] n = 5000, m1 = 1017, m2 = 984, t = 5000
11 Correct 1 ms 640 KB [OK, No] n = 5000, m1 = 1495, m2 = 1506, t = 5000
12 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 974, m2 = 1026, t = 2501
13 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1022, m2 = 978, t = 2501
14 Correct 2 ms 640 KB [OK, Yes] n = 5000, m1 = 1019, m2 = 981, t = 2501
15 Correct 67 ms 640 KB [OK, Yes] n = 5000, m1 = 1298, m2 = 1367, t = 2501
16 Correct 976 ms 660 KB [OK, No] n = 5000, m1 = 1301, m2 = 1360, t = 2501
17 Correct 340 ms 640 KB [OK, Yes] n = 5000, m1 = 1320, m2 = 1315, t = 2501
18 Correct 390 ms 544 KB [OK, No] n = 5000, m1 = 1195, m2 = 1135, t = 2501
19 Correct 435 ms 656 KB [OK, No] n = 5000, m1 = 1148, m2 = 1202, t = 2501
20 Correct 622 ms 652 KB [OK, No] n = 5000, m1 = 1147, m2 = 1179, t = 2501
21 Correct 405 ms 648 KB [OK, No] n = 5000, m1 = 1163, m2 = 1146, t = 2501
22 Correct 931 ms 664 KB [OK, No] n = 5000, m1 = 1145, m2 = 1184, t = 2501
23 Correct 894 ms 640 KB [OK, No] n = 5000, m1 = 1172, m2 = 1150, t = 2501
24 Incorrect 3 ms 544 KB [No solution found] n = 20, m1 = 12, m2 = 9, t = 3
25 Halted 0 ms 0 KB -