Submission #114389

#	Time	Username	Problem	Language	Result	Execution time	Memory
114389		sebinkim	World of Tank (innopolis2018_final_E)	C++14	30 / 100	3 ms	512 KiB

E

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

bool B[1010101][2];
int dp[1010101][2], C[1010101][2];

int n, m1, m2, t;

void print(int y)
{
	vector <int> V1;
	vector <pii> V2;
	
	int i;
	
	for(i=0; i<=n; i++){
		if(C[i][y]){
			y = 1 - y;
			V1.push_back(i);
			if(B[i][y]) return;
		}
		
		if(dp[i][y] == 0){
			V2.emplace_back(i, y);
		}
	}
	
	printf("Yes\n");
	
	printf("%d\n", V1.size());
	for(int &t: V1) printf("%d ", t); printf("\n");
	
	printf("%d\n", V2.size());
	for(pii &t: V2) printf("%d %d\n", t.first, t.second + 1);
}

int main()
{
	int i, j, x;
	
	scanf("%d%d%d%d", &n, &m1, &m2, &t);
	
	if(n > 1e6) return 0;
	
	for(i=1; i<=m1; i++){
		scanf("%d", &x);
		B[x][0] = 1;
	}
	
	for(i=1; i<=m2; i++){
		scanf("%d", &x);
		B[x][1] = 1;
	}
	
	dp[n + 1][0] = 1e9;
	dp[n + 1][1] = 1e9;
	
	for(i=n; i>=0; i--){
		for(j=0; j<2; j++){
			if(B[i][j]){
				dp[i][j] = min(-1, dp[i + 1][j] - t + 1);
				
				if(!B[i][1 - j]){
					if(dp[i + 1][1 - j] >= -1 && dp[i][j] < min(-1, dp[i + 1][1 - j] - t + 1)){
						C[i][j] = 1;
						dp[i][j] = min(-1, dp[i + 1][1 - j] - t + 1);
					}
				}
			}
			else{
				dp[i][j] = dp[i + 1][j] + 1;
				
				if(!B[i][1 - j]){
					if(dp[i + 1][1 - j] >= -1 && dp[i][j] < dp[i + 1][1 - j] + 1){
						C[i][j] = 1;
						dp[i][j] = dp[i + 1][1 - j] + 1;
					}
				}
			}
		}
	}
	
	if(dp[0][0] >= t) print(0);
	else if(dp[0][1] >= t) print(1);
	else printf("No\n");
	
	return 0;
}

Compilation message (stderr)

E.cpp: In function 'void print(int)':
E.cpp:33:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", V1.size());
                 ~~~~~~~~~^
E.cpp:34:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int &t: V1) printf("%d ", t); printf("\n");
  ^~~
E.cpp:34:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int &t: V1) printf("%d ", t); printf("\n");
                                    ^~~~~~
E.cpp:36:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", V2.size());
                 ~~~~~~~~~^
E.cpp: In function 'int main()':
E.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m1, &m2, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
E.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

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