Submission #1279457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279457		khanhphucscratch	Naval battle (CEOI24_battle)	C++20	36 / 100	2231 ms	117880 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> nw[200005], ne[200005], sw[200005], se[200005], north[200005], west[200005], south[200005], east[200005];
vector<int> vec1, vec2, vec3, vec4;
pair<int, int> p[200005];
int dir[200005];
bool visited[200005];
inline bool cmp(const int x, const int y)
{
    return p[x] < p[y];
}
inline bool cmp2(const int x, const int y)
{
    return p[x] > p[y];
}
inline int dis(int x, int y)
{
    return (abs(p[x].first - p[y].first)+abs(p[x].second - p[y].second))/2;
}
bool dfs(int u, int pardis)
{
    if(visited[u] == 1) return 0;
    visited[u] = 1;
    int diag1 = upper_bound(vec1.begin(), vec1.end(), p[u].first - p[u].second) - vec1.begin();
    int diag2 = upper_bound(vec2.begin(), vec2.end(), p[u].first + p[u].second) - vec2.begin();
    int diag3;
    if(dir[u]%2 == 1) diag3 = upper_bound(vec4.begin(), vec4.end(), p[u].second) - vec4.begin();
    else diag3 = upper_bound(vec3.begin(), vec3.end(), p[u].first) - vec3.begin();
    vector<int>::iterator le, ri, mid;
    if(dir[u] == 0){
        le = upper_bound(ne[diag2].begin(), ne[diag2].end()-1, u, cmp2);
        ri = upper_bound(se[diag1].begin(), se[diag1].end()-1, u, cmp);
        mid = upper_bound(east[diag3].begin(), east[diag3].end()-1, u, cmp);
    }
    else if(dir[u] == 1){
        le = upper_bound(se[diag1].begin(), se[diag1].end()-1, u, cmp);
        ri = upper_bound(sw[diag2].begin(), sw[diag2].end()-1, u, cmp);
        mid = upper_bound(south[diag3].begin(), south[diag3].end()-1, u, cmp);
    }
    else if(dir[u] == 2){
        le = upper_bound(sw[diag2].begin(), sw[diag2].end()-1, u, cmp);
        ri = upper_bound(nw[diag1].begin(), nw[diag1].end()-1, u, cmp2);
        mid = upper_bound(west[diag3].begin(), west[diag3].end()-1, u, cmp2);
    }
    else{
        le = upper_bound(nw[diag1].begin(), nw[diag1].end()-1, u, cmp2);
        ri = upper_bound(ne[diag2].begin(), ne[diag2].end()-1, u, cmp2);
        mid = upper_bound(north[diag3].begin(), north[diag3].end()-1, u, cmp2);
    }
    //Now we do some iterations
    while(*le != 0 || *ri != 0 || *mid != 0){
    //cerr<<"A"<<u<<" "<<*le<<" "<<*ri<<" "<<*mid<<endl;
        bool ok = 0, good1 = 0, good2 = 0, good3 = 0;
        int redis;
        if((*ri == 0 || dis(*le, u) <= dis(*ri, u)) && (*mid == 0 || dis(*le, u) <= dis(*mid, u))){
            if(dis(*le, u) > pardis) break;
            good1 = 1;
            if(*le != 0 && dir[*le] == (dir[u]+1)%4){
                redis = dis(*le, u);
                ok |= dfs(*le, dis(*le, u));
            }
        }
        if((*le == 0 || dis(*le, u) >= dis(*ri, u)) && (*mid == 0 || dis(*mid, u) >= dis(*ri, u))){
            if(dis(*ri, u) > pardis) break;
            good2 = 1;
            if(*ri != 0 && dir[*ri] == (dir[u]+3)%4){
                redis = dis(*ri, u);
                ok |= dfs(*ri, dis(*ri, u));
            }
        }
        if((*le == 0 || dis(*le, u) >= dis(*mid, u)) && (*ri == 0 || dis(*mid, u) <= dis(*ri, u))){
            if(dis(*mid, u) > pardis) break;
            good3 = 1;
            if(*mid != 0 && dir[*mid] == (dir[u]+2)%4){
                redis = dis(*mid, u);
                ok |= dfs(*mid, dis(*mid, u));
            }
        }
        if(good1 == 1) le++;
        if(good2 == 1) ri++;
        if(good3 == 1) mid++;
        if(ok == 1){
            if(redis == pardis) return 1;
            else return 0;
        }
    }
    return 1;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        char x;
        cin>>p[i].first>>p[i].second>>x;
        swap(p[i].first, p[i].second);
        if(x == 'E') dir[i] = 0;
        if(x == 'S') dir[i] = 1;
        if(x == 'W') dir[i] = 2;
        if(x == 'N') dir[i] = 3;
    }
    for(int i = 1; i <= n; i++){
        vec1.push_back(p[i].first-p[i].second);
    }
    p[0] = make_pair(3e9, 3e9);
    sort(vec1.begin(), vec1.end());
    vec1.erase(unique(vec1.begin(), vec1.end()), vec1.end());
    for(int i = 1; i <= n; i++){
        int pl = upper_bound(vec1.begin(), vec1.end(), p[i].first-p[i].second)-vec1.begin();
        se[pl].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        sort(se[i].begin(), se[i].end(), cmp);
        nw[i] = se[i];
        reverse(nw[i].begin(), nw[i].end());
        se[i].push_back(0); nw[i].push_back(0);
    }
    /**/
    for(int i = 1; i <= n; i++){
        vec2.push_back(p[i].first+p[i].second);
    }
    sort(vec2.begin(), vec2.end());
    vec2.erase(unique(vec2.begin(), vec2.end()), vec2.end());
    for(int i = 1; i <= n; i++){
        int pl = upper_bound(vec2.begin(), vec2.end(), p[i].first+p[i].second)-vec2.begin();
        sw[pl].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        sort(sw[i].begin(), sw[i].end(), cmp);
        ne[i] = sw[i];
        reverse(ne[i].begin(), ne[i].end());
        sw[i].push_back(0); ne[i].push_back(0);
    }
    /**/
    for(int i = 1; i <= n; i++){
        vec3.push_back(p[i].first);
    }
    sort(vec3.begin(), vec3.end());
    vec3.erase(unique(vec3.begin(), vec3.end()), vec3.end());
    for(int i = 1; i <= n; i++){
        int pl = upper_bound(vec3.begin(), vec3.end(), p[i].first)-vec3.begin();
        east[pl].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        sort(east[i].begin(), east[i].end(), cmp);
        west[i] = east[i];
        reverse(west[i].begin(), west[i].end());
        west[i].push_back(0); east[i].push_back(0);
    }
    /**/
    for(int i = 1; i <= n; i++){
        vec4.push_back(p[i].second);
    }
    sort(vec4.begin(), vec4.end());
    vec4.erase(unique(vec4.begin(), vec4.end()), vec4.end());
    for(int i = 1; i <= n; i++){
        int pl = upper_bound(vec4.begin(), vec4.end(), p[i].first)-vec4.begin();
        south[pl].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        sort(south[i].begin(), south[i].end(), cmp);
        north[i] = south[i];
        reverse(north[i].begin(), north[i].end());
        south[i].push_back(0); north[i].push_back(0);
    }
    for(int i = 1; i <= n; i++) if(dfs(i, 1e18) == 1) 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