Submission #283589

#	Time	Username	Problem	Language	Result	Execution time	Memory
283589		arnold518	World of Tank (innopolis2018_final_E)	C++14	30 / 100	976 ms	664 KiB

E

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 27
• Subtask 5: 0 / 23