Submission #1087757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087757		1xlc	Naval battle (CEOI24_battle)	C++14	6 / 100	2031 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#define MAX 200005
#define rp(a,b) for(int i=a;i<b;i++)
#define rep(a,b,x) for(int x=a;x<b;x++)
#define piii pair<long long,pair<long long,long long>>
#define debug cout<<"-1\n";
using namespace std;

int main()
{
    int n;cin>>n;
    int x[MAX],y[MAX];
    char c[MAX];
    rp(0,n){
        cin>>x[i]>>y[i];
        cin>>c[i];
    }
    priority_queue<piii,vector<piii>,greater<piii>>pq;
    rp(0,n){
        rep(0,n,j){
            if(i!=j){
                if(c[i]=='E'){
                    if(c[j]=='E'){
                        continue;
                    }else if(c[j]=='W'){
                        if(y[i]==y[j]){
                           pq.push({abs(x[i]-x[j])/2,{i,j}});
                        }
                    }else if(c[j]=='N'){
                        if(y[j]-y[i]==x[j]-x[i]){
                            pq.push({y[j]-y[i],{i,j}});
                        }
                    }else{
                        if(y[i]-y[j]==x[j]-x[i]){
                            pq.push({y[i]-y[j],{i,j}});
                        }
                    }
                }else if(c[i]=='W'){
                    if(c[j]=='E'){
                        if(y[i]==y[j]){
                           pq.push({abs(x[i]-x[j])/2,{i,j}});
                        }
                    }else if(c[j]=='W'){
                        continue;
                    }else if(c[j]=='N'){
                        if(y[j]-y[i]==x[i]-x[j]){
                            pq.push({y[j]-y[i],{i,j}});
                        }
                    }else{
                        if(y[i]-y[j]==x[i]-x[j]){
                            pq.push({y[i]-y[j],{i,j}});
                        }
                    }
                }else if(c[i]=='N'){
                    if(c[j]=='E'){
                        if(y[i]-y[j]==x[i]-x[j]){
                            pq.push({y[i]-y[j],{i,j}});
                        }
                    }else if(c[j]=='W'){
                        if(y[i]-y[j]==x[j]-x[i]){
                            pq.push({y[i]-y[j],{i,j}});
                        }
                    }else if(c[j]=='N'){
                        continue;
                    }else{
                        if(x[i]==x[j]){
                            pq.push({abs(y[i]-y[j])/2,{i,j}});
                        }
                    }
                }
            }
        }
    }
    bool visited[MAX]={0};
    while(pq.size()>0){
        piii t=pq.top();pq.pop();
        queue<pair<int,int>>q;
        if(!visited[t.second.first]&&!visited[t.second.second]){
           q.push({t.second.first,t.second.second});
        }
        while(t.first==pq.top().first&&pq.size()>0){
            t=pq.top();
            pq.pop();
            if(!visited[t.second.first]&&!visited[t.second.second]){
                q.push({t.second.first,t.second.second});
            }
        }
        while(q.size()>0){
            pair<int,int> t=q.front();q.pop();
            visited[t.first]=true;
            visited[t.second]=true;
        }
    }
    rp(0,n){
        if(!visited[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