제출 #1227159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227159		Malix	Naval battle (CEOI24_battle)	C++20	6 / 100	3115 ms	800260 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

//0-N, 1-S, 2-E, 3-W

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
   int n;cin>>n;
   vii a(n,vi(3,0));
   REP(i,0,n){
    int x,y;cin>>x>>y;
    char z;cin>>z;
    swap(x,y);
    a[i][0]=x;
    a[i][1]=y;
    if(z=='S')a[i][2]=1;
    else if(z=='E')a[i][2]=2;
    else if(z=='W')a[i][2]=3;
   }
   priority_queue<ti,vector<ti>,greater<ti>> pq;
   vi b(n,0);
   REP(i,0,n)REP(j,i+1,n)if(i!=j){
    int x=i,y=j;
    if(a[x][2]>a[y][2])swap(x,y);
    if(a[x][2]==0){
        if(a[y][2]==1&&a[x][1]==a[y][1])pq.push({abs(a[x][0]-a[y][0])/2,x,y});
        if(a[y][2]==2&&abs(a[x][1]-a[y][1])==abs(a[x][0]-a[y][0])&&a[x][0]>a[y][0]&&a[x][1]>a[y][1])pq.push({abs(a[x][0]-a[y][0]),x,y});
        if(a[y][2]==3&&abs(a[x][1]-a[y][1])==abs(a[x][0]-a[y][0])&&a[x][0]>a[y][0]&&a[x][1]<a[y][1])pq.push({abs(a[x][0]-a[y][0]),x,y});
    }
    else if(a[x][2]==1){
        if(a[y][2]==2&&abs(a[x][1]-a[y][1])==abs(a[x][0]-a[y][0])&&a[x][0]<a[y][0]&&a[x][1]>a[y][1])pq.push({abs(a[x][0]-a[y][0]),x,y});
        if(a[y][2]==3&&abs(a[x][1]-a[y][1])==abs(a[x][0]-a[y][0])&&a[x][0]<a[y][0]&&a[x][1]<a[y][1])pq.push({abs(a[x][0]-a[y][0]),x,y});
    }
    else if(a[x][2]==2){
        if(a[y][2]==3&&a[x][0]==a[y][0])pq.push({abs(a[x][1]-a[y][1])/2,x,y});
    }
   }
   int lst=0;
   while(!pq.empty()){
    auto [z,x,y]=pq.top();
    pq.pop();
    if(lst!=z&&(b[x]||b[y]))continue;
    b[x]=1;b[y]=1;
    lst=z;
   }
   REP(i,0,n)if(!b[i])cout<<i+1<<"\n";
}

• 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