Submission #1159999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159999		eggx50000	Naval battle (CEOI24_battle)	C++20	36 / 100	395 ms	30944 KiB

Main

#include <iostream>
#include <vector>
#include <deque>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;
const ll mod = 100000007;

int n;
bool fl[200099], vis[200099];
char c;
int x, y;
map <int, vector<int>> mp1, mp2;
struct Da{
    char c;
    int x, y, mk, mki, ind, t, d;
    bool fi;

    bool operator <(const Da &a) const{
        return ind < a.ind;
    }


} arr[200099];

bool compx(const Da &a, const Da &b){
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

bool compy(const Da &a, const Da &b){
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

void p(int x, int y, int k){
    mp1[x + y].push_back(k);
    mp2[x - y].push_back(k);
}

int dst(int a, int b){
    return (abs(arr[a].x - arr[b].x) + abs(arr[a].y - arr[b].y));
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d %d %c", &y,  &x, &c);
        arr[i] = {c, x, y, -1, 0, i, 2000000000, false};

    }
    sort(arr + 1, arr + n + 1, compx);
    for(int i = 1; i <= n; i ++){
        int e = i;
        while(e < n && arr[e + 1].x == arr[i].x) e ++;
        int li = 0;
        for(int j = i; j <= e; j ++){
            if(arr[j].c == 'N' || arr[j].c == 'S') continue;
            if(arr[j].c == 'W'){
                if(li){
                    arr[j].mk = (arr[j].y + arr[li].y) / 2;
                    arr[j].mki = arr[li].ind;
                    arr[j].d = abs(arr[j].y - arr[li].y);
                }
                else arr[j].mk = -2000000000;
                li = 0;
            }
            else li = j;
        }
        li = 0;
        for(int j = e; j >= i; j --){
            if(arr[j].c == 'N' || arr[j].c == 'S') continue;
            if(arr[j].c == 'E'){
                if(li){
                    arr[j].mk = (arr[j].y + arr[li].y) / 2;
                    arr[j].mki = arr[li].ind;
                    arr[j].d = abs(arr[j].y - arr[li].y);
                }
                else arr[j].mk = 2000000000;
                li = 0;
            }
            else li = j;
        }
        i = e;
    }
    sort(arr + 1, arr + n + 1, compy);
    for(int i = 1; i <= n; i ++){
        int e = i;
        while(e < n && arr[i].y == arr[e + 1].y) e ++;
        int li = 0;
        for(int j = i; j <= e; j ++){
            if(arr[j].c == 'W' || arr[j].c == 'E') continue;
            if(arr[j].c == 'N'){
                if(li){
                    arr[j].mk = (arr[j].x + arr[li].x) / 2;
                    arr[j].mki = arr[li].ind;
                    arr[j].d = abs(arr[j].x - arr[li].x);
                }
                else arr[j].mk = -2000000000;
                li = 0;
            }
            else li = j;
        }
        li = 0;
        for(int j = e; j >= i; j --){
            if(arr[j].c == 'W' || arr[j].c == 'E') continue;
            if(arr[j].c == 'S'){
                if(li){
                    arr[j].mk = (arr[j].x + arr[li].x) / 2;
                    arr[j].mki = arr[li].ind;
                    arr[j].d = abs(arr[j].x - arr[li].x);
                }
                else arr[j].mk = 2000000000;
                li = 0;
            }
            else li = j;
        }
        e = i;
    }
    sort(arr + 1, arr + n + 1, compx);
    for(int i = 1; i <= n; i ++){ //S
        if(arr[i].c == 'N') continue;
        if(arr[i].c == 'S') p(arr[i].x, arr[i].y, i);
        else if(arr[i].c == 'W'){
            while(mp2.find(arr[i].x - arr[i].y) != mp2.end() && mp2[arr[i].x - arr[i].y].size()){
                int b = mp2[arr[i].x - arr[i].y].back();
                mp2[arr[i].x - arr[i].y].pop_back();
                if(arr[b].mk < arr[i].x || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
        else{
            while(mp1.find(arr[i].x + arr[i].y) != mp1.end() && mp1[arr[i].x + arr[i].y].size()){
                int b = mp1[arr[i].x + arr[i].y].back();
                mp1[arr[i].x + arr[i].y].pop_back();
                if(arr[b].mk < arr[i].x || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
    }
    mp1.clear();mp2.clear();
    memset(vis, 0, sizeof(vis));

    for(int i = n; i >= 1; i --){ //N
        if(arr[i].c == 'S') continue;
        if(arr[i].c == 'N') p(arr[i].x, arr[i].y, i);
        else if(arr[i].c == 'E'){
            while(mp2.find(arr[i].x - arr[i].y) != mp2.end() && mp2[arr[i].x - arr[i].y].size()){
                int b = mp2[arr[i].x - arr[i].y].back();
                mp2[arr[i].x - arr[i].y].pop_back();
                if(arr[b].mk > arr[i].x || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
        else{
            while(mp1.find(arr[i].x + arr[i].y) != mp1.end() && mp1[arr[i].x + arr[i].y].size()){
                int b = mp1[arr[i].x + arr[i].y].back();
                mp1[arr[i].x + arr[i].y].pop_back();
                if(arr[b].mk > arr[i].x || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
    }
    sort(arr + 1, arr + n + 1, compy);
    mp1.clear();mp2.clear();
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++){ //E
        if(arr[i].c == 'W') continue;
        if(arr[i].c == 'E') p(arr[i].x, arr[i].y, i);
        else if(arr[i].c == 'N'){
            while(mp2.find(arr[i].x - arr[i].y) != mp2.end() && mp2[arr[i].x - arr[i].y].size()){
                int b = mp2[arr[i].x - arr[i].y].back();
                mp2[arr[i].x - arr[i].y].pop_back();
                if(arr[b].mk < arr[i].y || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
        else{
            while(mp1.find(arr[i].x + arr[i].y) != mp1.end() && mp1[arr[i].x + arr[i].y].size()){
                int b = mp1[arr[i].x + arr[i].y].back();
                mp1[arr[i].x + arr[i].y].pop_back();
                if(arr[b].mk < arr[i].y || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
    }
    mp1.clear();mp2.clear();
    memset(vis, 0, sizeof(vis));

    for(int i = n; i >= 1; i --){ //W
        if(arr[i].c == 'E') continue;
        if(arr[i].c == 'W') p(arr[i].x, arr[i].y, i);
        else if(arr[i].c == 'S'){
            while(mp2.find(arr[i].x - arr[i].y) != mp2.end() && mp2[arr[i].x - arr[i].y].size()){
                int b = mp2[arr[i].x - arr[i].y].back();
                mp2[arr[i].x - arr[i].y].pop_back();
                if(arr[b].mk > arr[i].y || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
        else{
            while(mp1.find(arr[i].x + arr[i].y) != mp1.end() && mp1[arr[i].x + arr[i].y].size()){
                int b = mp1[arr[i].x + arr[i].y].back();
                mp1[arr[i].x + arr[i].y].pop_back();
                if(arr[b].mk > arr[i].y || vis[b]) continue;
                arr[i].fi = true;
                vis[b] = true;
                arr[i].t = min(arr[i].t, dst(i, b));
                break;
            }
        }
    }
    sort(arr + 1, arr + n + 1);
    for(int i = 1; i <= n; i ++){
        if(arr[i].fi || (arr[i].mki && arr[i].d <= arr[arr[i].mki].t)) fl[i] = true;
    }
    for(int i = 1; i <= n; i ++){
        if(!fl[i]) printf("%d\n", i);
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d %c", &y,  &x, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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