Submission #1068765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068765		naneosmic	Naval battle (CEOI24_battle)	C++14	0 / 100	3042 ms	7248 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
signed main(){
    int n;
    cin>>n;
    vector<pair<pair<int,int>,int>>v(n);
    vector<bool>gone(n,false);
    vector<bool>escaped(n,false);
    for(int i=0;i<n;i++){
        int x,y;char c;
        cin>>x>>y>>c;
        int num;
        if(c=='N'){
            num=0;
        }else if(c=='S'){
            num=1;
        }else if(c=='E'){
            num=2;
        }else if(c=='W'){
            num=3;
        }
        v[i]=make_pair(make_pair(x,y),num);
    }
    for(int i=0;i<n;i++){
        if(!gone[i]){
            pair<pair<int,int>,int>cur=v[i];
            int num1=cur.second;
            set<pair<int,int>>collisions;
            for(int j=0;j<n;j++){
                if(!gone[j]){
                    pair<pair<int,int>,int>novi=v[j];
                    int num2=novi.second;
                    if(num1==0&&num2==1){
                        if(cur.first.first==novi.first.first){
                            collisions.insert(make_pair((cur.first.second-novi.first.second)/2,j));
                        }
                    }else if(num1==0&&num2==2){
                        if(cur.first.first+novi.first.second==cur.first.second+novi.first.first){
                            collisions.insert(make_pair(cur.first.second-novi.first.second,j));
                        }
                    }else if(num1==0&&num2==3){
                        if(cur.first.first+novi.first.first==cur.first.second+novi.first.second){
                            collisions.insert(make_pair(cur.first.second-novi.first.second,j));
                        }
                    }else if(num1==1&&num2==0){
                        if(cur.first.first==novi.first.first){
                            collisions.insert(make_pair((novi.first.second-cur.first.second)/2,j));
                        }
                    }else if(num1==1&&num2==2){
                        if(cur.first.first+novi.first.first==cur.first.second+novi.first.second){
                            collisions.insert(make_pair(novi.first.second-cur.first.second,j));
                        }
                    }else if(num1==1&&num2==3){
                        if(cur.first.first+novi.first.second==cur.first.second+novi.first.first){
                            collisions.insert(make_pair(novi.first.second-cur.first.second,j));
                        }
                    }else if(num1==2&&num2==0){
                        if(cur.first.first+novi.first.second==cur.first.second+novi.first.first){
                            collisions.insert(make_pair(novi.first.second-cur.first.second,j));
                        }
                    }else if(num1==2&&num2==1){
                        if(cur.first.first+novi.first.first==cur.first.second+novi.first.second){
                            collisions.insert(make_pair(cur.first.second-novi.first.second,j));
                        }
                    }else if(num1==2&&num2==3){
                        if(cur.first.second==novi.first.second){
                            collisions.insert(make_pair((novi.first.first-cur.first.first)/2,j));
                        }
                    }else if(num1==3&&num2==0){
                        if(cur.first.first+novi.first.first==cur.first.second+novi.first.second){
                            collisions.insert(make_pair(novi.first.second-cur.first.second,j));
                        }
                    }else if(num1==3&&num2==1){
                        if(cur.first.first+novi.first.second==cur.first.second+novi.first.first){
                            collisions.insert(make_pair(cur.first.second-novi.first.second,j));
                        }
                    }else if(num1==3&&num2==2){
                        if(cur.first.second==novi.first.second){
                            collisions.insert(make_pair((cur.first.first-novi.first.first)/2,j));
                        }
                    }
                }
            }
            auto it1=collisions.lower_bound(make_pair(0,0));
            if(it1==collisions.end()){
                gone[i]=true;
                escaped[i]=true;
                continue;
            }
            int val=(*it1).first;
            int num=0;
            vector<int>tobeerased(4,i);
            while(it1!=collisions.end()){
                if((*it1).first==val){
                    tobeerased[num]=(*it1).second;
                }else{
                    break;
                }
                it1++;
                num++;
            }
            gone[tobeerased[0]]=true;
            gone[tobeerased[1]]=true;
            gone[tobeerased[2]]=true;
            gone[tobeerased[3]]=true;
        }
    }
    for(int i=0;i<n;i++){
        if(escaped[i]){
            cout<<i+1<<" ";
        }
    }
    cout<<'\n';
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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