Submission #1073437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073437		ProtonDecay314	Naval battle (CEOI24_battle)	C++17	6 / 100	3017 ms	4816 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 = max(abs(s1.x - s2.x), abs(s1.y - s2.y));

    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;
    for(int i = 0; i < n; i++) {
        int cn = s.size();
        if(cn == 1) {
            ans.pb(s[0].i);
            return ans;
        } else if(cn == 0) return ans;
        int mnmv = INF(int);
        vs new_s;

        // Find min distance
        for(int j = 0; j < cn - 1; j++) {
            for(int k = j + 1; k < cn; k++) {
                if(will_collide(s[j], s[k])) {
                    mnmv = min(mnmv, abs(s[j].x - s[k].x));
                }
            }
        }

        if(mnmv == INF(int)) {
            // No annihilating pairs found, break out
            break;
        }

        // Advance ships by min distance
        for(int j = 0; j < cn; j ++) {
            s[j].x = s[j].x + dir[s[j].d].fi * mnmv;
            s[j].y = s[j].y + dir[s[j].d].se * mnmv;
        }

        sort(s.begin(), s.end(), [](ship s1, ship s2) {
            return s1.x > s2.x || (s1.x == s2.x && s1.y > s2.y);
        });

        for(int j = 0; j < cn; j++) {
            if(j == 0 && (s[j].x != s[j + 1].x || s[j].y != s[j + 1].y)) {
                new_s.pb(s[j]);
            } else if(j == cn - 1 && (s[j].x != s[j - 1].x || s[j].y != s[j - 1].y)) {
                new_s.pb(s[j]);
            } else if(0 < j && j < cn - 1 && (s[j].x != s[j + 1].x || s[j].y != s[j + 1].y) && (s[j].x != s[j - 1].x || s[j].y != s[j - 1].y)) {
                new_s.pb(s[j]);
            }
        }

        s = new_s;
    }

    int cn = s.size();

    for(int i = 0; i < cn; i++) {
        ans.pb(s[i].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:119:13: warning: 'dv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |         s.pb({x, y, dv, i});
      |         ~~~~^~~~~~~~~~~~~~~

• 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