Submission #1228558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228558		prism7k	Naval battle (CEOI24_battle)	C++20	6 / 100	3055 ms	794608 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct ship {
	int x, y;
	int dir;
	int dt = -1;
};

int main() {
	int n; cin >> n;
	vector<ship> ships;
	for(int i = 0; i < n; ++i) {
		int x, y;
		char dir;
		cin >> x >> y >> dir;
		int dir_translated = -1;
		if(dir == 'N') dir_translated = 0;
		else if(dir == 'E') dir_translated = 1;
		else if(dir == 'S') dir_translated = 2;
		else dir_translated = 3;
		ships.push_back({x, y, dir_translated});
	}
	// for each ship, calculate the min crash time;
	vector<tuple<int, int, int>> crashes;
	for(int i = 0; i < n - 1; ++i) {
		for(int j = i + 1; j < n; ++j) {
			if(i == j) continue;
			if(ships[i].dir == ships[j].dir) continue;
			ship a = ships[i], b = ships[j];
			int ind_1 = i, ind_2 = j;
			if(a.dir > b.dir) {
				swap(a, b);
				swap(ind_1, ind_2);
			}
			//~ cout << "adir = " << a.dir << " bdir = " << b.dir << "\n";
			if(a.dir == 0 && b.dir == 1 && (a.x - b.x) == (a.y - b.y) && a.x > b.x) {
				crashes.push_back({a.x - b.x, ind_1, ind_2});
			} else if(a.dir == 0 && b.dir == 2 && a.x == b.x && a.y < b.y) {
				crashes.push_back({(b.y - a.y) / 2, ind_1, ind_2});
			} else if(a.dir == 0 && b.dir == 3 && (b.x - a.x) == (a.y - b.y) && b.x > a.x) {
				crashes.push_back({b.x - a.x, ind_1, ind_2});
			} else if(a.dir == 1 && b.dir == 2 && (b.x - a.x) == (a.y - b.y) && b.x > a.x) {
				crashes.push_back({b.x - a.x, ind_1, ind_2});
			} else if(a.dir == 1 && b.dir == 3 && a.y == b.y && a.x < b.x) {
				crashes.push_back({(b.x - a.x) / 2, ind_1, ind_2});
			} else if(a.dir == 2 && b.dir == 3 && (b.y - a.y) == (b.x - a.x) && b.y > a.y) {
				crashes.push_back({b.y - a.y, ind_1, ind_2});
			}
			//~ cout << "crashes size = " << (int)crashes.size() << "\n";
		}
	}
	sort(crashes.begin(), crashes.end());
	int sz = (int)crashes.size();
	for(int i = 0; i < sz; ++i) {
		int time = get<0>(crashes[i]);
		//~ cout << "time = " << time << "\n";
		int j = get<1>(crashes[i]), k = get<2>(crashes[i]);
		ship a = ships[j], b = ships[k];
		if(a.dt == -1 && b.dt == -1) { // both ships crash
			ships[j].dt = time;
			ships[k].dt = time;
		} else if((a.dt == time && b.dt == -1) || (a.dt == -1 && b.dt == time)) {
			ships[j].dt = time;
			ships[k].dt = time;
		}
	}
	
	for(int i = 0; i < n; ++i) {
		if(ships[i].dt == -1) cout << i + 1 << "\n";
	}
}

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