제출 #1074877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074877		pawned	Naval battle (CEOI24_battle)	C++17	0 / 100	376 ms	36772 KiB

Main

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

ll norm(ll x, ll y) {
	x %= y;
	x += y;
	x %= y;
	return x;
}

ll intersect(pair<int, ii> s1, pair<int, ii> s2) {
//	cout<<"at "<<"("<<s1.fi<<", "<<s1.se.fi<<", "<<s1.se.se<<"); ("<<s2.fi<<", "<<s2.se.fi<<", "<<s2.se.se<<")"<<endl;
	// time if intersect, -1 if not
	if (s1.fi > s2.fi)	// ensure first is less than second
		swap(s1, s2);
	if (s1.fi == s2.fi)	// if same direction, never intersect
		return -1;
	if (s1.fi == 0 && s2.fi == 1) {	// x coord const, first increasing
		if (s1.se.fi != s2.se.fi)
			return -1;
		if (norm(s1.se.se + s2.se.se) == 1 || s1.se.se > s2.se.se)
			return -1;
		return abs(s2.se.se - s1.se.se) / 2;
	}
	if (s1.fi == 2 && s2.fi == 3) {	// y coord const, first increasing
		if (s1.se.se != s2.se.se)
			return -1;
		if (norm(s1.se.fi + s2.se.fi) == 1 || s1.se.fi > s2.se.fi)
			return -1;
		return abs(s2.se.fi - s1.se.fi) / 2;
	}
	// first going N/S, other going E/W
	ii ins = {s1.se.fi, s2.se.se};
//	cout<<"ins: "<<ins.fi<<", "<<ins.se<<endl;
	ll t1 = ins.se - s1.se.se;
	if (s1.fi == 1)
		t1 = -t1;
	ll t2 = ins.fi - s2.se.fi;
//	cout<<"t1, t2: "<<t1<<" "<<t2<<endl;
	if (s2.fi == 3)
		t2 = -t2;
	if (t1 == t2 && t1 > 0)
		return t1;
	return -1;
}

int main() {
	map<char, int> conv = {{'S', 0}, {'N', 1}, {'E', 2}, {'W', 3}};
	fastIO();
	int N;
	cin>>N;
	vector<pair<int, ii>> ships;
	// {type, {x, y}}
	map<ll, vector<pair<ii, ii>>> alld;	// all on diagonal x+y=i, going down
	// set of {{x, y}, {type, id}}
	for (int i = 0; i < N; i++) {
		ll x, y; char d;
		cin>>x>>y>>d;
		ships.pb({conv[d], {x, y}});
		alld[x + y].pb({{x, y}, {conv[d], i}});
	}
/*	cout<<"ships: ";
	for (pair<int, ii> p : ships)
		cout<<"("<<p.fi<<", "<<p.se.fi<<", "<<p.se.se<<"); ";
	cout<<endl;*/
	vector<bool> alive(N, true);	// still alive
	for (pair<ll, vector<pair<ii, ii>>> pr : alld) {
//		cout<<"at "<<pr.fi<<endl;
		sort(pr.se.begin(), pr.se.end());
		int K = pr.se.size();
		vector<char> dir;	// A = east, B = south
		vi idx;
		for (int j = 0; j < K; j++) {
			if (pr.se[j].se.fi == 2)
				dir.pb('A');
			else
				dir.pb('B');
			idx.pb(pr.se[j].se.se);
		}
/*		cout<<"K: "<<K<<endl;
		cout<<"dir: ";
		for (char c : dir)
			cout<<c<<" ";
		cout<<endl;
		cout<<"idx: ";
		for (int x : idx)
			cout<<x<<" ";
		cout<<endl;*/
		// remove all consec
		queue<int> q;	// all existing A, most recent on top
		for (int j = 0; j < K; j++) {
			if (dir[j] == 'A') {
				q.push(idx[j]);
			}
			else {
				if (!q.empty()) {
					int x = q.front();
					q.pop();
//					cout<<"removed "<<x<<" "<<idx[j]<<endl;
					alive[x] = false;
					alive[idx[j]] = false;
				}
			}
		}
	}
//	cout<<"ANSWER: "<<endl;
	for (int i = 0; i < N; i++) {
		if (alive[i])
			cout<<(i + 1)<<endl;
	}
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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