Submission #1197166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197166		user736482	Naval battle (CEOI24_battle)	C++20	30 / 100	1043 ms	100348 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
map<ll,set<pair<ll,ll>>>mp[6];
ll n,a,b,c;
char ch;
bool bad[200007];
set<pair<ll,pair<ll,ll>>>s;
vector<pair<char,pair<ll,ll>>>v;

bool czy(ll x,ll y,ll idx){
    if(v[x].ff>v[y].ff)swap(x,y);
    if(idx==0){
        x=v[x].ss.ss-v[y].ss.ss;
    }
    else{
        x=v[x].ss.ff-v[y].ss.ff;
    }
    if(idx==0 ||idx==2 || idx==5) return x>0;
    return x<0;
}

ll f2(ll x,ll y,ll z){
    if(z==0)return x;
    if(z==1)return y;
    if(z/2==1)return x+y;
    return x-y;
}
void f(ll idx,ll x){
    pair<ll,ll>pom=v[x].ss;
    a=pom.ff;
    b=pom.ss;
    ch=v[x].ff;
    auto it=mp[idx][f2(a,b,idx)].lower_bound({a*((bool)idx)+b*(!(bool)idx),x});
    if(it!=mp[idx][f2(a,b,idx)].begin() && v[(*prev(it)).ss].ff!=ch){
        ll curr=(*prev(it)).ss;
        if(czy(x,curr,idx))
        s.erase({max(abs(a-v[curr].ss.ff),abs(b-v[curr].ss.ss)),{min(curr,x),max(curr,x)}});
    }
    if(it!=--mp[idx][f2(a,b,idx)].end() && v[(*next(it)).ss].ff!=ch){
        ll curr=(*next(it)).ss;
        if(czy(x,curr,idx))
        s.erase({max(abs(a-v[curr].ss.ff),abs(b-v[curr].ss.ss)),{min(curr,x),max(curr,x)}});
    }
    if(it!=mp[idx][f2(a,b,idx)].begin() && it!=--mp[idx][f2(a,b,idx)].end() && v[(*next(it)).ss].ff!=v[(*prev(it)).ss].ff){
        ll curr=(*prev(it)).ss;
        x=(*next(it)).ss;
        if(czy(x,curr,idx))
        s.insert({max(abs(v[x].ss.ff-v[curr].ss.ff),abs(v[x].ss.ss-v[curr].ss.ss)),{min(curr,x),max(curr,x)}});
    }
}
void us(ll x){
    pair<ll,ll>pom=v[x].ss;
    a=pom.ff;
    b=pom.ss;
    ch=v[x].ff;
    if(ch=='N' || ch=='S'){
        f(0,x);
        mp[0][a].erase({a,x});
    }
    else{f(1,x);
        mp[1][b].erase({a,x});
    }
    if(ch=='N' || ch=='W'){f(2,x);
        mp[2][a+b].erase({a,x});
    }
    else{f(3,x);
        mp[3][a+b].erase({a,x});
    }
    if(ch=='N' || ch=='E'){f(4,x);
        mp[4][a-b].erase({a,x});
    }
    else{f(5,x);
        mp[5][a-b].erase({a,x});
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>a>>b>>ch;
        v.pb({ch,{a,b}});
        if(ch=='N' || ch=='S'){
            mp[0][a].insert({b,i});
        }
        else{
            mp[1][b].insert({a,i});
        }
        if(ch=='N' || ch=='W'){
            mp[2][a+b].insert({a,i});
        }
        else{
            mp[3][a+b].insert({a,i});
        }
        if(ch=='N' || ch=='E'){
            mp[4][a-b].insert({a,i});
        }
        else{
            mp[5][a-b].insert({a,i});
        }
    }
    for(ll i=0;i<6;i++){
        for(auto j : mp[i]){
            for(auto it=j.ss.begin();it!=j.ss.end() && it!=--j.ss.end();it++){
                if(v[(*next(it)).ss].ff!=v[(*it).ss].ff){
                    ll curr=(*it).ss;
                    ll x=(*next(it)).ss;
                    if(czy(x,curr,i))
                    s.insert({max(abs(v[x].ss.ff-v[curr].ss.ff),abs(v[x].ss.ss-v[curr].ss.ss)),{min(curr,x),max(curr,x)}});
                }
            }
        }
    }
    while(s.size()){
        ll ak=(*s.begin()).ff;
        vector<ll>vak;
        for(auto it=s.begin();it!=s.end() && (*it).ff==ak;it++){
            vak.pb((*it).ss.ff);
            vak.pb((*it).ss.ss);
        }
        for(ll i : vak){
            if(!bad[i]){
                bad[i]=1;
                us(i);
            }
        }
    }
    for(ll i=0;i<n;i++)if(!bad[i])cout<<i+1<<"\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: 30 / 30
• Subtask 7: 0 / 24