Submission #1098711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098711		Mighilon	Naval battle (CEOI24_battle)	C++17	100 / 100	2058 ms	201572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int mxN=1e7+1;

struct Point{
	int sign, pos, id;
};
bool operator<(Point&a,Point&b){
	return a.pos<b.pos;
}

struct Bad{
	int id1, id2, t;
};
bool operator<(const Bad&a,const Bad&b){
	return a.t<b.t;
}

priority_queue<Bad> pq;

void check(Point&a,Point&b){
	if(a.sign==1&&b.sign==-1)
		pq.push({a.id, b.id, a.pos-b.pos});
}

struct myList{
	list<Point> li;
	map<int, list<Point>::iterator> rit;
	void init(){
		vector<Point> a(all(li));
		sort(all(a));
		li=list<Point>(all(a));
		for(auto it=li.begin();it!=li.end();++it){
			rit[it->id]=it;
			if(next(it)!=li.end())
				check(*it,*next(it));
		}
	}
	void erase(int id){
		if(rit.find(id)!=rit.end()){
			auto it=rit[id];
			it=li.erase(it);
			if(it!=li.begin()&&it!=li.end()){
				check(*prev(it),*it);
			}
		}
	}
};
vector<map<int,myList>> lis(6);
vector<bool> p;

void insert(int t,int id,int x, int y,int sign){
	lis[t][x].li.push_back({sign,y,id});
}

void solve(){
	int n; 
	cin>>n;
	p.resize(n,1);
	vpi a(n);
	F0R(i,n){
		int x,y;char c;
		cin>>x>>y>>c;
		if(c=='N'||c=='S')insert(0,i,x,y,c=='S'?1:-1);
		if(c=='W'||c=='E')insert(1,i,y,x,c=='E'?1:-1);
		if(c=='S'||c=='W')insert(2,i,x-y,x+y,c=='S'?1:-1);
		if(c=='W'||c=='N')insert(3,i,x+y,x-y,c=='N'?1:-1);
		if(c=='N'||c=='E')insert(4,i,x-y,x+y,c=='E'?1:-1);
		if(c=='E'||c=='S')insert(5,i,x+y,x-y,c=='E'?1:-1);
		a[i]={x,y};
	}
	F0R(i,6){
		trav(j,lis[i]){
			j.s.init();
		}
	}
	while(!pq.empty()){
		int t=pq.top().t;
		vi e;
		while(!pq.empty()&&pq.top().t==t){
			auto [i,j,t2]=pq.top();
			pq.pop();
			if(p[i]&&p[j]){
				e.pb(i);
				e.pb(j);
			}
		}
		sort(all(e));
		e.erase(unique(all(e)),e.end());
		dbg(e);
		trav(i,e){
			p[i]=0;
			lis[0][a[i].f].erase(i);
			lis[1][a[i].s].erase(i);
			lis[2][a[i].f-a[i].s].erase(i);
			lis[3][a[i].f+a[i].s].erase(i);
			lis[4][a[i].f-a[i].s].erase(i);
			lis[5][a[i].f+a[i].s].erase(i);
		}
		while(!pq.empty()){
			if(p[pq.top().id1]&&p[pq.top().id2])break;
			else pq.pop();
		}
	}
	F0R(i,n){
		if(p[i])
			cout<<i+1<<nl;
	}
}

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

• 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: 30 / 30
• Subtask 7: 24 / 24