Submission #114404

#	Time	Username	Problem	Language	Result	Execution time	Memory
114404		sebinkim	World of Tank (innopolis2018_final_E)	C++14	77 / 100	237 ms	22620 KiB

E

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

bool B[2020202][2];
vector <int> X;
int D[2020202][2];
int dp[2020202][2], C[2020202][2];

int n, m1, m2, t;

void print(int y)
{
	vector <int> V1;
	vector <pii> V2;
	
	int i, j, l, r;
	
	for(i=0; i<n; i++){
		if(C[i][y]){
			y = 1 - y;
			V1.push_back(X[i]);
		}
		
		l = dp[i][y] - X[i + 1] + X[i]; r = dp[i][y];
//		printf("%d %d\n", l, r);
		if(l >= 0) continue;
		for(j=-(l+1)/t; j>=0 && -j*t <= r; j--){
			V2.emplace_back(X[i] + (r + j*t), y);
		}
	}
	
	sort(V2.begin(), V2.end());
	
	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, k, x;
	
	scanf("%d%d%d%d", &n, &m1, &m2, &t);
	
	if(n > 1e6) return 0;
	
	for(i=1; i<=m1; i++){
		scanf("%d", D[i]);
		X.push_back(D[i][0]);
		X.push_back(D[i][0] + 1);
	}
	
	for(i=1; i<=m2; i++){
		scanf("%d", D[i] + 1);
		X.push_back(D[i][1]);
		X.push_back(D[i][1] + 1);
	}
	
	X.push_back(0); X.push_back(n + 1);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for(i=1; i<=m1; i++){
		k = lower_bound(X.begin(), X.end(), D[i][0]) - X.begin();
		B[k][0] = 1;
	}
	
	for(i=1; i<=m2; i++){
		k = lower_bound(X.begin(), X.end(), D[i][1]) - X.begin();
		B[k][1] = 1;
	}
	
	n = X.size() - 1;
	
	dp[n][0] = 1e9;
	dp[n][1] = 1e9;
	
	for(i=n-1; 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] + X[i + 1] - X[i];
				
				if(!B[i][1 - j]){
					if(dp[i + 1][1 - j] >= -X[i + 1] + X[i] && dp[i][j] < dp[i + 1][1 - j] + X[i + 1] - X[i]){
						C[i][j] = 1;
						dp[i][j] = dp[i + 1][1 - j] + X[i + 1] - X[i];
					}
				}
			}
		}
	}
	
	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:39: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:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int &t: V1) printf("%d ", t); printf("\n");
  ^~~
E.cpp:40: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:42: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:48:15: warning: unused variable 'x' [-Wunused-variable]
  int i, j, k, x;
               ^
E.cpp:50: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:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", D[i]);
   ~~~~~^~~~~~~~~~~~
E.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", D[i] + 1);
   ~~~~~^~~~~~~~~~~~~~~~

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