Submission #1134449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134449		Aiperiii	Naval battle (CEOI24_battle)	C++20	76 / 100	1231 ms	1114112 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
vector <int> ind[4];

signed main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    int n;
    cin>>n;
    
    vector <int> x(n),y(n),ok(n,1);
    vector <char> d(n);
    
    
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i]>>d[i];
        if(d[i]=='N'){
            ind[0].pb(i);
        }
        else if(d[i]=='S'){
            ind[1].pb(i);
        }
        else if(d[i]=='E'){
            ind[2].pb(i);
        }
        else{
            ind[3].pb(i);
        }
    }
    
    
    
    if(ind[0].size()==0 && ind[3].size()==0){
        
        map <int, vector <pair <pair <int,int>,int > > > mp;
        for(auto i : ind[1]){
            mp[x[i]+y[i]].pb({{x[i],y[i]},i});
        }
        for(auto i : ind[2]){
            mp[x[i]+y[i]].pb({{x[i],y[i]},i});
        }
        
        for(auto x : mp){
            sort(all(mp[x.ff]));
        }
        for(auto x : mp){
            
            vector <int> pr;
            for(auto i : x.ss){
                if(d[i.ss]=='E')pr.pb(i.ss);
                else{
                    if(!pr.empty()){
                        ok[pr.back()]=0;
                        ok[i.ss]=0;
                        pr.pop_back();
                    }
                }
                
                //cout<<i.ff.ff<<" "<<i.ff.ss<<" "<<i.ss<<"\n";
            }
        }
        for(int i=0;i<n;i++){
            if(ok[i])cout<<i+1<<"\n";
        }
        return 0;
    }
    
   
    vector <pair <int,pair <int,int> > > v;
    
    
    for(auto i :  ind[0]){
        
        for(auto j : ind[2]){
            
            if(x[i]-x[j]==y[i]-y[j]){
                
                if(x[i]-x[j]>0)v.pb({x[i]-x[j],{i,j}});
                
            }
        }
        for(auto j : ind[3]){
            
            if(x[j]-x[i]==y[i]-y[j]){
                if(x[j]-x[i]>0)v.pb({x[j]-x[i],{i,j}});
               
            }
        }
    }
    for(auto i :  ind[1]){
        
        for(auto j : ind[2]){
            
            
            if(x[i]-x[j]==y[j]-y[i]){
                
                if(x[i]-x[j]>0)v.pb({x[i]-x[j],{i,j}});
                
            }
        }
        for(auto j : ind[3]){
            
            if(x[j]-x[i]==y[j]-y[i]){
                if(x[j]-x[i]>0)v.pb({x[j]-x[i],{i,j}});
                
            }
        }
    }
    for(auto i :  ind[0]){
        for(auto j : ind[1]){
            if(abs(x[i]-x[j])==0){
                if((y[i]-y[j])>0) v.pb({(y[i]-y[j])/2,{i,j}});
                
            }
            
        }
    }
    for(auto i :  ind[2]){
        for(auto j : ind[3]){
            if(abs(y[i]-y[j])==0){
                if(x[j]-x[i]>0) v.pb({(x[j]-x[i])/2,{i,j}});
               
            }
        }
    }
    
    
    sort(all(v));
    vector <int> pr;
    
    int val=0;
    for(auto x : v){
       // cout<<x.ff<<" "<<x.ss.ff<<" "<<x.ss.ss<<"\n";
        if(val!=x.ff){
            val=x.ff;
            for(auto i  : pr){
                ok[i]=0;
            }
            pr.clear();
        }
        
        if(ok[x.ss.ff] && ok[x.ss.ss]){
            pr.pb(x.ss.ff);
            pr.pb(x.ss.ss);
        }
    }
    for(auto i  : pr){
        ok[i]=0;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(ok[i])cout<<i+1<<"\n";
    }
    
}
/*

*/

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