Submission #283580

#	Time	Username	Problem	Language	Result	Execution time	Memory
283580		arnold518	World of Tank (innopolis2018_final_E)	C++14	0 / 100	175 ms	624 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];

bool solve()
{
	memset(bef, -1, sizeof(bef));
	queue<pii> Q;
	Q.push({1, 0}); bef[1][0]=0;
	pii p={-1, -1};
	while(!Q.empty())
	{
		pii now=Q.front(); Q.pop();
		if(now.second==N+1) { p=now; continue; }
		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});
		}
	}

	if(p.first==-1) return 0;
	vector<int> ans;
	while(1)
	{
		if(p==pii(1, 0)) 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());
	printf("Yes\n");
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%d ", it); printf("\n");
	return 1;
}

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;

	if(solve()) return !printf("0\n");
	for(int i=1; i<=M1; i++)
	{
		S[1][A[i]]=0;
		if(solve()) return !printf("1\n%d 1\n", A[i]);
		S[1][A[i]]=1;
	}
	for(int i=1; i<=M2; i++)
	{
		S[2][B[i]]=0;
		if(solve()) return !printf("2\n%d 2\n", B[i]);
		S[2][B[i]]=1;
	}
	printf("No\n");
}

Compilation message (stderr)

E.cpp: In function 'bool solve()':
E.cpp:50:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   50 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
E.cpp:51:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |  for(auto it : ans) printf("%d ", it); printf("\n");
      |  ^~~
E.cpp:51:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |  for(auto it : ans) printf("%d ", it); printf("\n");
      |                                        ^~~~~~
E.cpp: In function 'int main()':
E.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d%d%d%d", &N, &M1, &M2, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.cpp:58:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  for(int i=1; i<=M1; i++) scanf("%d", &A[i]), S[1][A[i]]=1;
      |                           ~~~~~^~~~~~~~~~~~~
E.cpp:59:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  for(int i=1; i<=M2; i++) scanf("%d", &B[i]), S[2][B[i]]=1;
      |                           ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 27
• Subtask 5: 0 / 23