Submission #115251

#	Time	Username	Problem	Language	Result	Execution time	Memory
115251		gs14004	World of Tank (innopolis2018_final_E)	C++17	77 / 100	102 ms	19688 KiB

E

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 1000005;

vector<int> v[2];
bool vis[MAXN][2];
bool trk[MAXN][2];
int dp[MAXN][2];
int n, t;

bool findCut(){
	for(auto &i : v[0]) vis[i][0] = 1;
	for(auto &i : v[1]) vis[i][1] = 1;
	dp[0][1] = -2e9;
	for(int i=1; i<=n; i++){
		for(int j=0; j<2; j++){
			if(!vis[i-1][j] && dp[i-1][j] < min(dp[i-1][j^1], t)){
				dp[i][j] = min(dp[i-1][j^1], t) + 1;
				trk[i][j] = 1;
			}
			else{
				dp[i][j] = dp[i-1][j] + 1;
			}
			if(vis[i][j]){
				dp[i][j] -= t;
				if(dp[i][j] <= 0) dp[i][j] = -2e9;
			}
		}
	}
	return max(dp[n][0], dp[n][1]) >= 0;
}

void trace(){
	int pos = 0;
	if(dp[n][0] < 0) pos = 1;
	vector<pi> boom;
	vector<int> trans;
	for(int i=n; i; i--){
		if(vis[i][pos]){
			int where = i - dp[i][pos];
			where = max(where, 1);
			boom.emplace_back(where, pos + 1);
			dp[i][pos] += t;
		}
		if(trk[i][pos]){
			pos ^= 1;
			trans.push_back(i - 1);
		}
	}
	assert(pos == 0);
	reverse(trans.begin(), trans.end());
	reverse(boom.begin(), boom.end());
	cout << trans.size() << endl;
	for(auto &i : trans) printf("%d ", i);
	cout << endl <<  boom.size() << endl;
	for(auto &i : boom) printf("%d %d\n", i.first, i.second);
}

int main(){
	int t0, t1;
	scanf("%d %d %d %d",&n,&t0,&t1,&t);
  assert(n <= 1000000);
	v[0].resize(t0);
	v[1].resize(t1);
	for(int i=0; i<2; i++){
		for(auto &j : v[i]){
			scanf("%d",&j);
		}
	}
	if(!findCut()){
		puts("No");
		return 0;
	}
	puts("Yes");
	trace();
}

Compilation message (stderr)

E.cpp: In function 'int main()':
E.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&n,&t0,&t1,&t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
E.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&j);
    ~~~~~^~~~~~~~~

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