Submission #1140567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140567		adiyer	Naval battle (CEOI24_battle)	C++20	30 / 100	301 ms	65772 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define F first
#define S second

using namespace std;

typedef long long ll;

const int N = 2e5 + 11;

ll n;

pair < pair < ll, ll >, ll > a[N];

vector < pair < ll, ll > > v[4];

map < ll, set < pair < ll, ll > > > mp[4];

map < pair < pair < ll, ll >, ll >, bool > del;

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(ll i = 1; i <= n; i++){
    char d;
    ll x, y, tp;
    cin >> x >> y >> d;
    if(d == 'E') tp = 0;
    if(d == 'S') tp = 1;
    if(d == 'W') tp = 2;
    if(d == 'N') tp = 3;
    a[i] = {{x, y}, tp};
    mp[tp][x + y].insert({x, y});
    v[tp].push_back({x, y});
  }
  for(ll i = 0; i < 4; i++) sort(all(v[i])), reverse(all(v[i]));
  for(auto [x, y] : v[0]){
    if(mp[1][x + y].upper_bound({x, 0}) == mp[1][x + y].end()) continue;
    auto it = *mp[1][x + y].upper_bound({x, y});
    mp[1][x + y].erase(it);
    del[{{it.F, it.S}, 1}] = 1;
    del[{{x, y}, 0}] = 1;
  }
  for(ll i = 1; i <= n; i++){
    if(del[a[i]]) continue;
    cout << i << ' ';
  }
}

• 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