Submission #1137548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137548		KaleemRazaSyed	Naval battle (CEOI24_battle)	C++20	46 / 100	916 ms	106204 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int inf = 2e9;

pair<int,int> V(char c)
{
  if(c == 'S') return {0, 1};
  if(c == 'N') return {0, -1};
  if(c == 'E') return {1, 0};
  return {-1, 0};
}

int D(int x1, int y1, char d1, int x2, int y2, char d2)
{

  if(x1 == x2 && y1 == y2) return 0;

  if(d1 == d2) return inf;

  if(x1 < x2 && (V(d1).first == -1 || V(d2).first == 1 || (V(d1).first == 0 && V(d2).first == 0))) return inf;
  if(x1 > x2 && (V(d1).first == 1 || V(d2).first == -1 || (V(d1).first == 0 && V(d2).first == 0))) return inf;
  if(y1 < y2 && (V(d1).second == -1 || V(d2).second == 1 || (V(d1).second == 0 && V(d2).second == 0))) return inf;
  if(y1 > y2 && (V(d1).second == 1 || V(d2).second == -1 || (V(d1).second == 0 && V(d2).second == 0))) return inf;
  if(x1 == x2 && (V(d1).first != V(d2).first)) return inf;
  if(y1 == y2 && (V(d1).second != V(d2).second)) return inf;
  
  int tx = -1, ty = -1;

  if(x1 != x2)
    {
      int d = abs(V(d1).first) + abs(V(d2).first);
      tx = abs(x1 - x2) / d;
    }
  
  if(y1 != y2)
    {
      int d = abs(V(d1).second) + abs(V(d2).second);
      ty = abs(y1 - y2) / d;
    }
  if(tx == -1 || ty == -1 || tx == ty)
    return max(tx, ty);
  return inf;
}

void solve(int n)
{
  vector<vector<int> > vec;
  int x[n], y[n];
  char d[n];
  int t[n] = {};
  fill(t, t + n, inf);
  for(int i = 0; i < n; i ++)
    cin >> x[i] >> y[i] >> d[i];

  for(int i = 0; i < n; i ++)
    for(int j = i + 1; j < n; j ++)
      {
	int X = D(x[i], y[i], d[i], x[j], y[j], d[j]);
	if(X != inf)
	  vec.push_back({X, i, j});
	  
      }
  sort(vec.begin(), vec.end());
  for(auto v : vec)
    {
      int d = v[0], i = v[1], j = v[2];
      if(t[i] == inf && t[j] == inf)
	t[i] = t[j] = d;
      else if(t[i] == inf && t[j] == d)
	t[i] = d;
      else if(t[j] == inf && t[i] == d)
	t[j] = d;
    }

  for(int i = 0; i < n; i ++)
    if(t[i] == inf)
      cout << i + 1 << '\n';
}

int main()
{
  int n;
  cin >> n;
  if(n <= 5000)
    {
      solve(n);
      return 0;
    }

  vector<vector<int> > vec, st;
  char c[n];

  bool dead[n] = {};
  
  for(int i = 0; i < n; i ++)
    {
      int x, y;
      cin >> x >> y >> c[i];
      vec.push_back({x, -y, i});
    }

  sort(vec.begin(), vec.end());

  for(int i = 1; i < n; i ++)
    if(vec[i - 1][0] == vec[i][0] && vec[i - 1][1] == vec[i][1])
      dead[vec[i - 1][2]] = dead[vec[i][2]] = true;
  
  for(int i = 0; i < n; i ++)
    if(!dead[vec[i][2]])
      st.push_back(vec[i]);

  set<vector<int> > S;
  int add = 0;
  
  for(int i = 0; i < st.size(); i ++)
    {
      if(i > 0)
	add += st[i][0] - st[i - 1][0];
      else
	add += st[i][0];

      if(c[st[i][2]] == 'E')
	S.insert({-st[i][1] + add, -st[i][0], st[i][2]});
      else
	{
	  auto it = S.lower_bound({-st[i][1], -inf, -inf});
	  if(it == S.end() || it->at(0) == -st[i][1]) continue;
	  dead[it->at(2)] = dead[st[i][2]] = true;
	  S.erase(it);
	}
      
    }
  for(int i = 0; i < n; i ++)
    if(!dead[i])
      cout << i << '\n';
  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: 0 / 30
• Subtask 7: 0 / 24