Submission #1094739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094739		epicci23	Naval battle (CEOI24_battle)	C++17	100 / 100	1627 ms	161012 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;

vector<bool> dead,vis;
vector<array<int,3>> v;
map<int,set<array<int,2>>> ekle[4];
map<int,set<array<int,2>>> cikar[4];
map<int,set<array<int,2>>> ver[2][2];
map<int,set<array<int,2>>> hor[2][2];

array<int,2> xd;

pair<int,vector<int>> get_min(int c,int cur=INF){
  int a=v[c][0],b=v[c][1],d=v[c][2];
  xd={b,0};
  //cout << "bakalim: " << c << ' ' << d  << '\n';
  vector<int> res;
  if(d==0){
    auto it = hor[1][b&1][a].lower_bound(xd);
    if(it!=hor[1][b&1][a].end() && cur>=((*it)[0]-b)/2){
      if(cur>((*it)[0]-b)/2) res.clear();
      cur=((*it)[0]-b)/2;
      res.push_back((*it)[1]);
    }
    it = ekle[2][a+b].lower_bound(xd);
    if(it!=ekle[2][a+b].end() && cur>=(*it)[0]-b){
      if(cur>(*it)[0]-b) res.clear();
      cur=(*it)[0]-b;
      res.push_back((*it)[1]);
    }
    it = cikar[3][a-b].lower_bound(xd);
    if(it!=cikar[3][a-b].end() && cur>=(*it)[0]-b){
      if(cur>(*it)[0]-b) res.clear();
      cur=(*it)[0]-b;
      res.push_back((*it)[1]);
    }
  }
  else if(d==1){
    auto it = hor[0][b&1][a].lower_bound(xd);
    if(it!=hor[0][b&1][a].begin() && cur>=(b-(*--it)[0])/2){
      if(cur>(b-(*it)[0])/2) res.clear();
      cur=(b-(*it)[0])/2;
      res.push_back((*it)[1]);
    }
    it = cikar[2][a-b].lower_bound(xd);
    if(it!=cikar[2][a-b].begin() && cur>=b-(*--it)[0]){
      if(cur>b-(*it)[0]) res.clear();
      cur=b-(*it)[0];
      res.push_back((*it)[1]);
    }
    it = ekle[3][a+b].lower_bound(xd);
    if(it!=ekle[3][a+b].begin() && cur>=b-(*--it)[0]){
      if(cur>b-(*it)[0]) res.clear();
      cur=b-(*it)[0];
      res.push_back((*it)[1]);
    }
  }
  else if(d==2){
    xd={a,0};
    auto it = ver[1][a&1][b].lower_bound(xd);
    if(it!=ver[1][a&1][b].end() && cur>=((*it)[0]-a)/2){
      if(cur>((*it)[0]-a)/2) res.clear();
      cur=((*it)[0]-a)/2;
      res.push_back((*it)[1]);
    }
    xd={b,0};
    it = cikar[1][a-b].lower_bound(xd);
    if(it!=cikar[1][a-b].end() && cur>=(*it)[0]-b){
      if(cur>(*it)[0]-b) res.clear();
      cur=(*it)[0]-b;
      res.push_back((*it)[1]);
    }
    it = ekle[0][a+b].lower_bound(xd);
    if(it!=ekle[0][a+b].begin() && cur>=b-(*--it)[0]){
      if(cur>b-(*it)[0]) res.clear();
      cur=b-(*it)[0];
      res.push_back((*it)[1]);
    }
  }
  else{
    xd={a,0};
    auto it = ver[0][a&1][b].lower_bound(xd);
    if(it!=ver[0][a&1][b].begin() && cur>=(a-(*--it)[0])/2){
      if(cur>(a-(*it)[0])/2) res.clear();
      cur=(a-(*it)[0])/2;
      res.push_back((*it)[1]);
    }
    xd={b,0};
    it = ekle[1][a+b].lower_bound(xd);
    if(it!=ekle[1][a+b].end() && cur>=(*it)[0]-b){
      if(cur>(*it)[0]-b) res.clear();
      cur=(*it)[0]-b;
      res.push_back((*it)[1]);
    }
    it = cikar[0][a-b].lower_bound(xd);
    if(it!=cikar[0][a-b].begin() && cur>=b-(*--it)[0]){
      if(cur>b-(*it)[0]) res.clear();
      cur=b-(*it)[0];
      res.push_back((*it)[1]);
    }
  }

  return {cur,res};
}

bool dfs(int c,int ti){
  if(dead[c] || vis[c]) return 0;
  vis[c]=1;
  //cout << "geldim: " << c << '\n';
  while(true){
   auto X = get_min(c);
   if(X.first>=ti) break;
   //cout << "lol: " << c << ' ' <<X.first << '\n';
   if(X.first<ti){
    vector<int> to_kill;
    for(int u:X.second){
      if(dfs(u,X.first)){
        to_kill.push_back(c);
        to_kill.push_back(u);
      }
    }
    for(int x:to_kill){
      if(dead[x]) continue;
      dead[x]=1;
      int a=v[x][0],b=v[x][1],d=v[x][2];
      ekle[d][a+b].erase({b,x});
      cikar[d][a-b].erase({b,x});
      if(d<=1) hor[d][b&1][a].erase({b,x});
      else ver[d-2][a&1][b].erase({a,x});
    }
    if(dead[c]) return 0;
   }
  }
  return 1;
}


void _(){
  int n; cin >> n;

  for(int i=0;i<n;i++){
  	int a,b,d;
  	char c;
  	cin >> b >> a >> c;
  	if(c=='E') d=0;
  	else if(c=='W') d=1; 
  	else if(c=='S') d=2;
  	else d=3;
  	v.push_back({a,b,d});
    
    ekle[d][a+b].insert({b,i});
    cikar[d][a-b].insert({b,i});
    if(d<=1) hor[d][b&1][a].insert({b,i});
    else ver[d-2][a&1][b].insert({a,i});
  }	
  dead.assign(n,0);
  vis.assign(n,0);

  for(int i=0;i<n;i++) dfs(i,INF);

  for(int i=0;i<n;i++){
    if(dead[i]) continue;
    cout << i + 1 << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  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