제출 #1137492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137492		KaleemRazaSyed	Naval battle (CEOI24_battle)	C++20	6 / 100	0 ms	328 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;
  int d = -1;

  if(x1 - x2 != 0)
    {
      bool s = false;
      if(x1 > x2) swap(x1, x2), swap(d1, d2), s = true;

      int delta = V(d1).first - V(d2).first;
      if(s) swap(d1, d2);

      if(delta == 0) return inf;
      d = (x2 - x1) / delta;
    }

  if(y1 - y2 != 0)
    {
      if(y1 > y2) swap(y1, y2), swap(d1, d2);
      int delta = V(d1).second - V(d2).second;
      if(delta == 0) return inf;
      int t = (y2 - y1) / delta;
      if(d != t)
	d = inf;
    }
  return d;
  
}

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: 0 / 12
• Subtask 3: 0 / 8
• Subtask 4: 0 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24