Submission #1140588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140588		adiyer	Naval battle (CEOI24_battle)	C++20	30 / 100	849 ms	147180 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;
const int mod = 1e9 + 7;
const ll inf = 1e12 + 11;

ll n;

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

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

map < ll, set < pair < ll, ll > > > sp[4], np[4], yp[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};
    sp[tp][x + y].insert({x, y});
    np[tp][x - y].insert({x, y});
    yp[tp][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]){
    pair < ll, ll > it1, it2, it3, it4;
    it1 = it2 = it3 = it4 = {inf, inf};
    if(sp[1][x + y].upper_bound({x, y}) != sp[1][x + y].end()){
      it1 = (*sp[1][x + y].upper_bound({x, y}));
    }
    if(np[3][x - y].upper_bound({x, y}) != np[3][x - y].end()){
      it2 = (*np[3][x - y].upper_bound({x, y}));
    }
    if(yp[2][y].upper_bound({x, y}) != yp[2][y].end()){
      it3 = (*yp[2][y].upper_bound({x, y}));
    }
    if(it1 == it4 && it2 == it4 && it3 == it4) continue;
    ll vx = it1.F - x, vy = it2.F - x, vz = it3.F - x, mn = min({vx, vy, vz});
    del[{{x, y}, 0}] = 1;
    if(vx == mn) del[{it1, 1}] = 1, sp[1][x + y].erase(it1);
    if(vy == mn) del[{it2, 3}] = 1, np[3][x + y].erase(it2);
    if(vz == mn) del[{it3, 2}] = 1, yp[2][x + y].erase(it3);
  }
  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