제출 #1134293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134293		amunduzbaev	Naval battle (CEOI24_battle)	C++20	46 / 100	507 ms	1114112 KiB

Main

#include "bits/stdc++.h"

using namespace std;

//~ #define int ll
typedef long long ll;
#define ar array

template<class T> bool umin(T& a, T b) { if(b < a) { a = b; return true; } return false; }
template<class T> bool umax(T& a, T b) { if(a < b) { a = b; return true; } return false; }

//~ const int mod = 1e9 + 7;
//~ void add(int& a, const int b){
	//~ a += b;
	//~ while(a >= mod) a -= mod;
	//~ while(a < 0) a += mod;
//~ }

const int inf = 1e9 + 5;

void solve(){
	int n; cin >> n;
	
	vector<int> x(n), y(n), d(n);
	
	vector<ar<int, 2>> coll[3] = {
		{ {0, 3}, {1, 2} },
		{ {2, 3}, {1, 0} },
		{ {1, 3}, {2, 0} }
	};
	
	for(int i=0;i<n;i++){
		char c;
		cin >> x[i] >> y[i] >> c;
		
		if(c == 'N') d[i] = 0;
		if(c == 'E') d[i] = 1;
		if(c == 'S') d[i] = 2;
		if(c == 'W') d[i] = 3;
	}
	
	auto check = [&](int i, int j){
		if(x[i] > x[j]) swap(i, j);
		if(x[i] == x[j] && y[i] > y[j]) swap(i, j);
		ar<int, 2> d_ = {d[i], d[j]};
		
		//~ cout<<i<<" "<<j<<" "<<d_[0]<<" "<<d_[1]<<"\n";
		
		if(x[i] + y[i] == x[j] + y[j] && (d_ == coll[0][0] || d_ == coll[0][1])){
			return abs(x[i] - x[j]);
		}
		if(x[i] - y[i] == x[j] - y[j] && (d_ == coll[1][0] || d_ == coll[1][1])) {
			return abs(x[i] - x[j]);
		}
		if(d_ == coll[2][0] && y[i] == y[j]) return (x[j] - x[i]) / 2;
		if(d_ == coll[2][1] && x[i] == x[j]) return (y[j] - y[i]) / 2;
		
		return inf + 1;
	};
	
	vector<vector<int>> t(n, vector<int>(n, inf));
	vector<ar<int, 3>> colt;
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			t[i][j] = check(i, j);
			
			if(t[i][j] <= inf) colt.push_back({t[i][j], i, j});
		}
	}
	
	sort(colt.begin(), colt.end());
	vector<int> liv(n, 1);
	for(int i=0;i<(int)colt.size();){
		int j = i;
		while(j < (int)colt.size() && colt[j][0] == colt[i][0]) j++;
		
		vector<int> dead;
		for(int k=i;k<j;k++){
			auto [time_, x, y] = colt[k];
			
			if(liv[x] && liv[y]){
				dead.push_back(x);
				dead.push_back(y);
			}
		}
		
		//~ cout<<colt[i][0]<<" : ";
		for(auto x : dead){
			//~ cout<<x<<" ";
			liv[x] = 0;
		}
		//~ cout<<"\n";
		
		i = j;
	}
	
	for(int i=0;i<n;i++){
		if(liv[i]) cout<<i + 1<<"\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int t = 1;
	
	//~ cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24