oj.uz

Submission #283580

# Submission time Handle Problem Language Result Execution time Memory
283580 2020-08-26T01:59:52 Z arnold518 World of Tank (innopolis2018_final_E) C++14
0 / 100
 175 ms 624 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];

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

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.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 1 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Incorrect 175 ms 624 KB Tank was in recharge!
10 Halted 0 ms 0 KB -

Subtask #2
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 1 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Incorrect 175 ms 624 KB Tank was in recharge!
10 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 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 1 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Incorrect 175 ms 624 KB Tank was in recharge!
10 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 1 ms 512 KB [OK, Yes] n = 5000, m1 = 764, m2 = 736, t = 5000
4 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 698, m2 = 802, t = 5000
5 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 720, m2 = 780, t = 5000
6 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 734, m2 = 766, t = 5000
7 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 997, m2 = 1003, t = 5000
8 Correct 1 ms 512 KB [OK, Yes] n = 5000, m1 = 1021, m2 = 979, t = 5000
9 Incorrect 175 ms 624 KB Tank was in recharge!
10 Halted 0 ms 0 KB -