Submission #1050877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050877		n1k	Naval battle (CEOI24_battle)	C++17	30 / 100	384 ms	36692 KiB

Main

#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

void umax(ll &a, ll b){
	a = max(a, b);
}

void solve(){
	int n; cin >> n;
	vector<int> r(n), c(n);
	vector<char> d(n);
	vector<int> dead(n);
	map<int, set<pair<int, int>>> d1;
	set<array<int, 3>> pq;
	for(int i=0; i<n; i++){
		cin >> c[i] >> r[i] >> d[i];
		d1[r[i]+c[i]].insert({r[i], i});
	}
	for(auto [id, v]:d1){
		for(auto it=v.begin(); next(it)!=v.end(); it++){
			auto [r1, i1]=*it;
			auto [r2, i2]=*next(it);
			if(d[i1]=='S' and d[i2]=='E'){
				pq.insert({abs(r[i1]-r[i2]), i1, i2});
			}
		}
		debug(id, v);
	}
	auto remove = [&](int i){
		dead[i]=1;
		auto it = d1[r[i]+c[i]].lower_bound({r[i], i});
		int il = -1, ir = -1;
		if(next(it)!=d1[r[i]+c[i]].end()){
			auto [_, i2] = *next(it);
			if(d[i]=='S' and d[i2]=='E'){
				pq.erase({abs(r[i]-r[i2]), i, i2});
			}
			ir=i2;
		}
		debug(i);
		debug(d1[r[i]+c[i]]);
		if(it!=d1[r[i]+c[i]].begin()){
			auto [_, i2] = *prev(it);
			if(d[i]=='E' and d[i2]=='S'){
				pq.erase({abs(r[i]-r[i2]), i2, i});
			}
			il=i2;
		}
		d1[r[i]+c[i]].erase(it);
		if(il!=-1 and ir!=-1 and d[il]=='S' and d[ir]=='E'){
			pq.insert({abs(r[il]-r[ir]), il, ir});
		}
	};
	while(pq.size()){
		debug(pq);
		vector<array<int, 3>> cur = {*pq.begin()};
		pq.erase(pq.begin());
		while(pq.size() and pq.begin()->front() == cur.front().front()){
			cur.push_back(*pq.begin());
			pq.erase(pq.begin());
		}
		debug(cur);
		// remove all ships that colide
		for(auto [t, i1, i2]:cur){
			debug(t, i1, i2);
			remove(i1);
			remove(i2);
		}
	}
	debug(dead);
	for(int i=0; i<n; i++){
		if(dead[i]) continue;
		cout << i + 1<< endl;
	}
}

int main(){
	solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:38:3: note: in expansion of macro 'debug'
   38 |   debug(id, v);
      |   ^~~~~
Main.cpp: In lambda function:
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:51:3: note: in expansion of macro 'debug'
   51 |   debug(i);
      |   ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:52:3: note: in expansion of macro 'debug'
   52 |   debug(d1[r[i]+c[i]]);
      |   ^~~~~
Main.cpp: In function 'void solve()':
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:66:3: note: in expansion of macro 'debug'
   66 |   debug(pq);
      |   ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:73:3: note: in expansion of macro 'debug'
   73 |   debug(cur);
      |   ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:76:4: note: in expansion of macro 'debug'
   76 |    debug(t, i1, i2);
      |    ^~~~~
Main.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
Main.cpp:81:2: note: in expansion of macro 'debug'
   81 |  debug(dead);
      |  ^~~~~

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