제출 #1137525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137525		KaleemRazaSyed	Naval battle (CEOI24_battle)	C++20	46 / 100	732 ms	106276 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;
    }

  
  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