제출 #1134258

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

Main

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define size(x) (int)(x).size()
#define int long long

typedef pair <int,int> pii;

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int inf = 1e12;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    
    int n; cin >> n;
    
    vector <ar<int,3>> a(n);
    
    for ( auto &[l, r, x]: a ){
		char t; cin >> l >> r >> t;
		
		if ( t == 'N' ) x = 0;
		if ( t == 'S' ) x = 1;
		if ( t == 'W' ) x = 2;
		if ( t == 'E' ) x = 3;
	}
	
	auto dis = [&](int i, int j){
		int x = max(abs(a[i][0] - a[j][0]), abs(a[i][1] - a[j][1]));
		
		if ( a[i][0] == a[j][0] ) x = abs(a[i][1] - a[j][1]) / 2;
		if ( a[i][1] == a[j][1] ) x = abs(a[i][0] - a[j][0]) / 2;
		
		return x;
	};
	
	auto ok = [&](int i, int j){
		if ( i == j ) return false;
		
		int x = dis(i, j);
		
		return (dx[a[i][2]] * x + a[i][0] == dx[a[j][2]] * x + a[j][0]) && 
			   (dy[a[i][2]] * x + a[i][1] == dy[a[j][2]] * x + a[j][1]);
	};
	
	vector <ar<int,3>> t;
	
	for ( int i = 0; i < n; i++ ){
		for ( int j = i + 1; j < n; j++ ){
			if ( ok(i, j) ) t.pb({dis(i, j), i, j});
		}
	}
	
	vector <int> dp(n, inf);
	
	sort(all(t));
	
	for ( auto &[v, x, y]: t ){
		if ( dp[x] < v || dp[y] < v ) continue;
		
		dp[x] = dp[y] = v;
	}
	
	for ( int i = 0; i < n; i++ ){
		if ( dp[i] == inf ) cout << i + 1 << '\n';
	}
	
	
	cout << '\n';
}

• 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