Submission #1073467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073467		ProtonDecay314	Naval battle (CEOI24_battle)	C++17	30 / 100	69 ms	11480 KiB

Main

// AM + DG
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define fi first
#define se second
#define IOS cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false)
#define pb push_back
#define INF(dtype) numeric_limits<dtype>::max()
#define NINF(dtype) numeric_limits<dtype>::min()

struct ship {
    int x, y, d, i;
};

vpi dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

typedef vector<ship> vs;

// bool will_collide(const ship& s1, const ship& s2) {
//     int linf = (abs(s1.x - s2.x) + abs(s1.y - s2.y)) >> 1ll;

//     int s0x = s1.x + dir[s1.d].fi * linf;
//     int s0y = s1.y + dir[s1.d].se * linf;
//     int s1x = s2.x + dir[s2.d].fi * linf;
//     int s1y = s2.y + dir[s2.d].se * linf;

//     return s0x == s1x && s0y == s1y;
// }

vi solve(int n, vs& s) {
    vi ans;
    sort(s.begin(), s.end(), [](ship s1, ship s2) {
        return s1.x + s1.y < s2.x + s2.y || (s1.x + s1.y == s2.x + s2.y && s1.x < s2.x);
    });

    vb inc(n, true);

    stack<ship> cs;

    for(int i = 0; i < n; i++) {
        if(i == 0 || s[i].x + s[i].y != s[i - 1].x + s[i - 1].y) {
            // Start a new stack
            while(!cs.empty()) cs.pop();

            if(s[i].d == 1) cs.push(s[i]);
        } else {
            if(s[i].d == 1) cs.push(s[i]);
            else {
                // pop from the stack, if possible
                if(cs.size() > 0) {
                    inc[cs.top().i] = false;
                    inc[s[i].i] = false;
                    cs.pop();
                }
            }
        }
    }

    for(int i = 0; i < n; i++) {
        if(inc[i]) ans.pb(i);
    }

    return ans;
}

int main() {
    IOS;

    int n;
    cin >> n;

    vs s;

    for(int i = 0; i < n; i++) {
        int x, y;
        char d;

        cin >> x >> y;
        cin >> d;

        int dv;

        if(d == 'N') dv = 0;
        if(d == 'E') dv = 1;
        if(d == 'S') dv = 2;
        if(d == 'W') dv = 3;

        s.pb({x, y, dv, i});
    }

    vi ans = solve(n, s);

    for(int v : ans) {
        cout << v + 1 << "\n";
    }
    cout << flush;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:98:13: warning: 'dv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |         s.pb({x, y, dv, i});
      |         ~~~~^~~~~~~~~~~~~~~

• 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