Submission #1103598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103598		SoMotThanhXuan	Naval battle (CEOI24_battle)	C++17	30 / 100	130 ms	21832 KiB

Main

// absolutely incredible
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define pb push_back
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
void updateMax(int &u, int v){
    if(v > u) u = v;
}
void updateMin(int &u, int v){
    if(v < u) u = v;
}
bool maximize(int &u, int v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimize(int &u, int v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
void updateMaxll(long long &u, long long v){
    if(v > u) u = v;
}
void updateMinll(long long &u, long long v){
    if(v < u) u = v;
}
bool maximizell(long long &u, long long v){
    if(v > u){
        u = v;
        return true;
    }
    return false;
}
bool minimizell(long long &u, long long v){
    if(v < u){
        u = v;
        return true;
    }
    return false;
}
int fastPow(int a, int n){
    if(n == 0) return 1;
    int t = fastPow(a, n >> 1);
    t = 1ll * t * t % mod;
    if(n & 1) t = 1ll * t * a % mod;
    return t;
}
void add(int &u, int v){
    u += v;
    if(u >= mod) u -= mod;
}
void sub(int &u, int v){
    u -= v;
    if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
struct Point{
    int x, y;
    char d;
    int intersect(const Point &rhs)const{
        if(d == rhs.d) return 0;
        int temp = abs(x - rhs.x) + abs(y - rhs.y);
        temp >>= 1;
        if(d == 'N'){
            if(rhs.d == 'E'){
                if(y - temp == rhs.y && rhs.x + temp == x) return temp;
                return 0;
            }
            if(rhs.d == 'S'){
                if(y - temp == rhs.y + temp && x == rhs.x) return temp;
                return 0;
            }
            if(y - temp == rhs.y && x == rhs.x - temp) return temp;
            return 0;
        }
        if(d == 'E'){
            if(rhs.d == 'N'){
                if(x + temp == rhs.x && rhs.y - temp == y) return temp;
                return 0;
            }
            if(rhs.d == 'W'){
                if(x + temp == rhs.x - temp && y == rhs.y) return temp;
                return 0;
            }
            if(x + temp == rhs.x && rhs.y + temp == y) return temp;
            return 0;
        }
        if(d == 'S'){
            if(rhs.d == 'N'){
                if(y + temp == rhs.y - temp && x == rhs.x) return temp;
                return 0;
            }
            if(rhs.d == 'E'){
                if(y + temp == rhs.y && rhs.x + temp  == x) return temp;
                return 0;
            }
            if(y + temp == rhs.y && rhs.x - temp == x) return temp;
            return 0;
        }
        if(rhs.d == 'N'){
            if(x - temp == rhs.x && rhs.y - temp == y) return temp;
            return 0;
        }
        if(rhs.d == 'E'){
            if(x - temp == rhs.x + temp && y == rhs.y) return temp;
            return 0;
        }
        if(x - temp == rhs.x && rhs.y + temp == y) return temp;
        return 0;
    }
}p[maxN];
const int INF = INT_MAX;
int N;
namespace subtask12345{
    bool check(){
        return N <= 5000;
    }
    const int maxT = 12497500 + 1;
    pair<int, pair<int, int>> t[maxT];
    int del[maxN];
    void solve(){
        int cnt = 0;
//        cout << p[3].intersect(p[4]) << '\n';
//        cout << abs(p[3].x - p[4].x) + abs(p[3].y - p[4].y) << '\n';
        FOR(i, 1, N){
            FOR(j, i + 1, N){
                int k = p[i].intersect(p[j]);
                if(k > 0)t[++cnt] = {k, {i, j}};
            }
        }
        sort(t + 1, t + 1 + cnt);
//        cout << cnt << "\n";
//        cout << p[2].intersect(p[6]) << '\n';
        FOR(i, 1, N)del[i] = INF;
//        cout << p[1].intersect(p[5]) << "\n";
        FOR(i, 1, cnt){
            int k = t[i].first;
            int pi = t[i].second.first;
            int pj = t[i].second.second;
            if(del[pi] < k || del[pj] < k)continue;
            del[pi] = del[pj] = k;
//            cout << pi << ' ' << pj << ' ' << k << "\n";
        }
//        FOR(i, 1, N){
//            cout << i << ' ' << del[i] << "\n";
//        }
        bool ok = true;
        FOR(i, 1, N){
            if(del[i] == INF)cout << i << "\n";
        }

    }

}
namespace subtask6{
    vector<pair<pair<int, int>, int>> v[maxN];
    int comp[maxN];
    bool check(){
        FOR(i, 1, N){
            if(p[i].d == 'S' || p[i].d == 'E') continue;
            return false;
        }
        return true;
    }
    bool del[maxN];
    void solve(){
        FOR(i, 1, N){
            comp[i] = p[i].x + p[i].y;
        }
        sort(comp + 1, comp + 1 + N);
        FOR(i, 1, N){
            int x = lower_bound(comp + 1, comp + 1 + N, p[i].x + p[i].y) - comp;
//            cout << i << ' ' << x << "\n";
            v[x].push_back({{p[i].x, p[i].y}, i});
        }
        stack<int> st;
        FOR(i, 1, N){
            sort(v[i].begin(), v[i].end());
//            cout << i << "\n";
//            for(pair<pair<int, int>, int> x : v[i]){
//                cout << x.second << ' ';
//            }
//            cout << "\n";
            while(st.size())st.pop();
            for(pair<pair<int, int>, int> x : v[i]){
                if(p[x.second].d == 'E')st.push(x.second);
                else{
                    if(!st.empty()){
                        del[st.top()] = del[x.second] = true;
                        st.pop();
                    }
                }
            }
        }
        FOR(i, 1, N){
            if(del[i] == false)cout << i << "\n";
        }
    }

}
void solve(){
    cin >> N;
    int x, y;
    char d;
    FOR(i, 1, N){
        cin >> x >> y >> d;
        p[i] = {x, y, d};
    }
//    if(subtask12345 :: check()) return subtask12345 :: solve();
    assert(subtask6 :: check());
    subtask6 :: solve();
}
int main(){
    if(fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void subtask12345::solve()':
Main.cpp:157:14: warning: unused variable 'ok' [-Wunused-variable]
  157 |         bool ok = true;
      |              ^~
Main.cpp: In function 'int main()':
Main.cpp:225:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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