Submission #1101378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101378		AlperenT_	Naval battle (CEOI24_battle)	C++17	36 / 100	198 ms	38400 KiB

Main

#include <bits/stdc++.h> 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define int long long 
#define ld long double 
using namespace std ;
const int maxn = 5e5 + 200 , maxq = 2e6+10 , mod = 1e9 + 7 , mod2 = 1e9 + 7, inf = 1e9 ;  
int m , x[maxn] , y[maxn] , t[maxn];
vector <pair<int ,pii> > vec; 
vector <pii> c[maxn] ;
bool cmp(pii a ,pii b){
    return (x[a.F] < x[b.F]) ;;
}

void sl(vector<int> a , vector <int> b){
    vector <int> cm , h;
    for(int i : a)cm.pb(x[i]+y[i]);
    for(int i : b)cm.pb(x[i]+y[i]);
    sort(all(cm));
    cm.resize(unique(all(cm)) - cm.begin()) ;
    for(int i : a){
        int s = lower_bound(all(cm) ,x[i]+y[i])-cm.begin() ;
        c[s].pb({i , 0});
    }
    for(int i : b){
        int s = lower_bound(all(cm) ,x[i]+y[i])-cm.begin() ;
        c[s].pb({i , 1});
    }
    rep(i ,0 , sz(cm)-1){
        vector <int> h ;
        sort(all(c[i]) , cmp);
        rep(j , 0 ,sz(c[i])-1){
            if(c[i][j].S==1){
                if(sz(h)==0){
                    continue ; 
                }
                vec.pb({x[c[i][j].F]-x[h.back()] , {c[i][j].F,h.back()} });
                h.pop_back();
            }else{
                h.pb(c[i][j].F); 
            }
        }
    }
    rep(i ,0 ,sz(cm)-1){
        c[i].clear() ;
    }
}

void sl2(vector <int> a , vector <int> b){
    vector <int> cm , h;
    for(int i : a)cm.pb(y[i]);
    for(int i : b)cm.pb(y[i]);
    sort(all(cm));
    cm.resize(unique(all(cm)) - cm.begin()) ;
    for(int i : a){
        int s = lower_bound(all(cm) ,y[i])-cm.begin() ;
        c[s].pb({i , 0});
    }
    for(int i : b){
        int s = lower_bound(all(cm) ,y[i])-cm.begin() ;
        c[s].pb({i , 1});
    }
    rep(i ,0 , sz(cm)-1){
        vector <int> h ;
        sort(all(c[i]) , cmp);
        rep(j , 0 ,sz(c[i])-1){
            if(c[i][j].S==1){
                if(sz(h)==0){
                    continue ; 
                }
                vec.pb({abs(x[c[i][j].F]-x[h.back()])/2 , {c[i][j].F,h.back()} });
                h.pop_back();
            }else{
                h.pb(c[i][j].F); 
            }
        }
    }
    rep(i ,0 ,sz(cm)-1){
        c[i].clear() ;
    }
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ; 
    cin >> m ;  
    vector <int> e,n,w,s ;
    rep(i ,1, m){
        char z; 
        cin >> x[i] >> y[i] >> z ; 
        if(z=='E'){
            e.pb(i);
        }
        if(z=='W'){
            w.pb(i);
        }
        if(z=='N'){
            n.pb(i);
        }
        if(z=='S'){
            s.pb(i);
        }
    }
    sl(e , s) ;
    rep(i ,1, m){
        y[i] *= -1 ;
    }
    sl(e , n);
    rep(i ,1 ,m){
        x[i]*=-1 ;
    }
    sl(w, n) ;
    rep(i , 1, m){
        y[i] *= -1 ;
    }
    sl(w, s) ;
    rep(i , 1, m){
        x[i] *= -1 ;
    }
    sl2(e, w); 
    rep(i ,1, m)swap(x[i],y[i]);
    sl2(s, n);
    sort(all(vec));
    rep(i ,1 ,m){
        t[i] = 0;
    }
    vector <int> his ;
    rep(i , 0 ,sz(vec)-1){
        if(i!=0 && vec[i-1].F != vec[i].F){
            while(sz(his)){
                t[his.back()] = 1;
                his.pop_back() ;
            }
        }
        pii x = vec[i].S ;
        if(t[x.F] ==1 || t[x.S]==1){
            continue ; 
        }
        his.pb(x.F);
        his.pb(x.S); 
    }
    for(int x : his)t[x] =1 ;
    rep(i ,1, m){
        if(t[i] ==0 ){
            cout << i << "\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: 30 / 30
• Subtask 7: 0 / 24