Submission #1045214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045214		c2zi6	Naval battle (CEOI24_battle)	C++14	6 / 100	355 ms	271776 KiB

Main

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct SHIP {
    int x, y;
    char dir;
    int ind;
};
struct ARROW {
    int cord;
    int open;
    int linenumber;
    SHIP ship;
};
bool operator<(const ARROW& a, const ARROW& b) {
    return a.cord < b.cord;
}
VI removed;
set<pair<int, PII>> orz;
struct LINE {
    set<ARROW> a;
    ARROW (*func)(SHIP);
    LINE(){}
    LINE(ARROW (*f)(SHIP)) {
        func = f;
    }
    bool add(SHIP s) {
        ARROW ret = func(s);
        if (ret.open == -1) return false;
        a.insert(ret);
        return true;
    }
    void init() {
        for (auto cur = a.begin(); cur != a.end(); cur++) {
            auto nxt = next(cur);
            if (nxt == a.end()) break;
            if (cur->open && !nxt->open) orz.insert({nxt->cord - cur->cord, {cur->ship.ind, nxt->ship.ind}});
        }
    }
    void rem(SHIP s) {
        int cord = func(s).cord;
        auto it = a.lower_bound(ARROW{cord});
        /*cout << "ARRAY: ";*/
        /*for (auto p : a) cout << p.cord << " "; cout << endl;*/
        /*cout << "TRYING TO REMOVE LOWER_BOUND(" << cord << ")" << endl;*/
        /*cout << endl;*/
        if (it != a.begin() && next(it) != a.end()) {
            if (prev(it)->open == true && next(it)->open == false) {
                orz.insert({next(it)->cord - prev(it)->cord,
                        {next(it)->ship.ind, prev(it)->ship.ind}});
            }
        }
        a.erase(it);
    }
};
 
void solve() {
    int n;
    cin >> n;
    vector<SHIP> a(n);
    vector<SHIP> original(n+1);
    rep(i, n) {
        int x, y;
        char d;
        cin >> x >> y >> d;
        a[i] = {x, y, d, i+1};
        original[i+1] = {x, y, d, i+1};
    }
    vector<vector<vector<LINE>::iterator>> whereis(n+1);
    vector<LINE> lines;
    lines.reserve(1e6);
    auto add = [&](ARROW(*f)(SHIP)) {
        bool flag = true;
        rep(i, n) {
            if (flag || lines.back().a.begin()->linenumber != f(a[i]).linenumber) {
                lines.pb(LINE(f));
                flag = false;
            }
            if (lines.back().add(a[i])) whereis[a[i].ind].pb(lines.end()-1);
        }
    };
    sort(all(a), [](SHIP a, SHIP b){return a.x < b.x;});
    add([](SHIP a){
            if (a.dir != 'N' && a.dir != 'S') return ARROW{-1, -1};
            return ARROW{a.y, a.dir == 'S', a.x, a};});
    sort(all(a), [](SHIP a, SHIP b){return a.y < b.y;});
    add([](SHIP a){
            if (a.dir != 'E' && a.dir != 'W') return ARROW{-1, -1};
            return ARROW{a.x, a.dir == 'E', a.y, a};});
    sort(all(a), [](SHIP a, SHIP b){return a.x+a.y < b.x+b.y;});
    add([](SHIP a){
            if (a.dir != 'E' && a.dir != 'S') return ARROW{-1, -1};
            return ARROW{a.x-a.y, a.dir == 'E', a.x+a.y, a};});
    add([](SHIP a){
            if (a.dir != 'N' && a.dir != 'W') return ARROW{-1, -1};
            return ARROW{a.x-a.y, a.dir == 'N', a.x+a.y, a};});
    sort(all(a), [](SHIP a, SHIP b){return a.x-a.y < b.x-b.y;});
    add([](SHIP a){
            if (a.dir != 'E' && a.dir != 'N') return ARROW{-1, -1};
            return ARROW{a.x+a.y, a.dir == 'E', a.x-a.y, a};});
    add([](SHIP a){
            if (a.dir != 'S' && a.dir != 'W') return ARROW{-1, -1};
            return ARROW{a.x+a.y, a.dir == 'S', a.x-a.y, a};});
 
    for (auto& ln : lines) ln.init();
    /*for (auto[time, p] : orz) {*/
    /*    cout << "AT TIME " << time << ", NODES (" << p.ff << ", " << p.ss << ")" << endl;*/
    /*}*/
    
    /*int ind = 0;*/
    /*for (auto ln : lines) {*/
    /*    ind++;*/
    /*    if (ln.a.size() == 0) continue;*/
    /*    cout << "LINE " << ind-1 << endl;*/
    /*    for (auto p : ln.a) cout << p.ship.ind << " ";*/
    /*    cout << endl;*/
    /*    for (auto p : ln.a) cout << p.cord << " ";*/
    /*    cout << endl;*/
    /*    for (auto p : ln.a) cout << p.open << " ";*/
    /*    cout << endl;*/
    /*}*/
 
    removed = VI(n+1);
    while (true) {
        vector<pair<int, PII>> buf;
        auto it = orz.begin();
        for (; it != orz.end(); it++) {
            if (it != orz.begin() && it->ff != prev(it)->ff) break;
            if (!removed[it->ss.ff] && !removed[it->ss.ss]) buf.pb({it->ff, it->ss});
        }
        while (it != orz.begin()) orz.erase(prev(it));
        /*cout << "AT THIS ROUND REMOVED FOLLOWING NODES" << endl;*/
        for (auto[W, P] : buf) {
            int i = P.ff, j = P.ss;
            /*cout << i << " " << j << endl;*/
            /*for (auto it : whereis[i]) {*/
            /*    cout << "REMOVED " << i << " FROM LINE " << it - lines.begin() << endl;*/
            /*}*/
            /*for (auto it : whereis[j]) {*/
            /*    cout << "REMOVED " << j << " FROM LINE " << it - lines.begin() << endl;*/
            /*}*/
            if (!removed[i]) for (auto it : whereis[i]) (*it).rem(original[i]);
            removed[i] = true;
            if (!removed[j]) for (auto it : whereis[j]) (*it).rem(original[j]);
            removed[j] = true;
        }
        if (orz.size() == 0) break;
    }
    replr(i, 1, n) if (!removed[i]) cout << i << endl;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	/*freopen("mincross.in", "r", stdin); */
	/*freopen("test.out", "w", stdout); */
	int t = 1;
	/*cin >> t; */
	while (t--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:162:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  162 |         for (auto[W, P] : buf) {
      |                  ^

• 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: 0 / 30
• Subtask 7: 0 / 24