Submission #1044048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044048		c2zi6	Naval battle (CEOI24_battle)	C++14	37 / 100	3087 ms	104976 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<typename T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef map<pair<int, char>, VI> LINE;

struct SHIP {
    int x, y;
    char d;
    int ind;
    void move(int s) {
        if (d == 'N') y -= s;
        else if (d == 'E') x += s;
        else if (d == 'S') y += s;
        else if (d == 'W') x -= s;
    }
    int limit(LINE& sum, LINE& dif, LINE& xmp, LINE& ymp) {
        int ret = +2e9;
        VI::iterator it;
        PII p;
        auto calclower = [&](LINE& line, int val, bool divide = false) {
            if ((it = lower_bound(all(line[p]), val)) != line[p].begin()) {
                int cur = val - *prev(it);
                if (divide) cur /= 2;
                setmin(ret, cur);
            }
        };
        auto calcupper = [&](LINE& line, int val, bool divide = false) {
            if ((it = upper_bound(all(line[p]), val)) != line[p].end()) {
                int cur = *it - val;
                if (divide) cur /= 2;
                setmin(ret, cur);
            }
        };
        if (d == 'N') {
            p = {x+y, 'W'};
            calcupper(sum, x);
            p = {x-y, 'E'};
            calclower(dif, x);
            p = {x, 'S'};
            calclower(xmp, y, true);
        } else if (d == 'E') {
            p = {x+y, 'S'};
            calcupper(sum, x);
            p = {x-y, 'N'};
            calcupper(dif, x);
            p = {y, 'W'};
            calcupper(ymp, x, true);
        } else if (d == 'S') {
            p = {x+y, 'E'};
            calclower(sum, x);
            p = {x-y, 'W'};
            calcupper(dif, x);
            p = {x, 'N'};
            calcupper(xmp, y, true);
        } else if (d == 'W') {
            p = {x+y, 'N'};
            calclower(sum, x);
            p = {x-y, 'S'};
            calclower(dif, x);
            p = {y, 'E'};
            calclower(ymp, x, true);
        }
        return ret;
    }
};

int minstep(vector<SHIP> a) {
    int n = a.size();
    LINE sum;
    LINE dif;
    LINE xmp;
    LINE ymp;
    for (auto[x, y, d, ind] : a) {
        sum[{x+y, d}].pb(x);
        dif[{x-y, d}].pb(x);
        xmp[{x, d}].pb(y);
        ymp[{y, d}].pb(x);
    }
    for (auto& p : sum) sort(all(p.ss));
    for (auto& p : dif) sort(all(p.ss));
    for (auto& p : xmp) sort(all(p.ss));
    for (auto& p : ymp) sort(all(p.ss));
    int ret = +2e9;
    for (auto p : a) {
        int cur = p.limit(sum, dif, xmp, ymp);
        /*cout << "CUR: " << cur << endl;*/
        setmin(ret, cur);
    }
    return ret;
}

void removesink(vector<SHIP>& a) {
    map<PII, int> cnt;
    for (auto[x, y, d, ind] : a) cnt[{x, y}]++;
    vector<SHIP> b;
    for (auto[x, y, d, ind] : a) {
        if (cnt[{x, y}] == 1) {
            b.pb({x, y, d, ind});
        }
    }
    a = b;
}

void solve() {
    int n;
    cin >> n;
    vector<SHIP> a(n);
    rep(i, n) {
        auto&[x, y, d, ind] = a[i];
        cin >> x >> y;
        cin >> d;
        ind = i+1;
    }
    while (true) {
        int step = minstep(a);
        if (step == +2e9) break;
        for (auto& p : a) p.move(step);
        removesink(a);
    }
    for (auto[x, y, d, ind] : a) cout << ind << 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 'int minstep(std::vector<SHIP>)':
Main.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |     for (auto[x, y, d, ind] : a) {
      |              ^
Main.cpp:97:9: warning: unused variable 'n' [-Wunused-variable]
   97 |     int n = a.size();
      |         ^
Main.cpp: In function 'void removesink(std::vector<SHIP>&)':
Main.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     for (auto[x, y, d, ind] : a) cnt[{x, y}]++;
      |              ^
Main.cpp:125:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |     for (auto[x, y, d, ind] : a) {
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         auto&[x, y, d, ind] = a[i];
      |              ^
Main.cpp:149:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |     for (auto[x, y, d, ind] : a) cout << ind << endl;
      |              ^

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 0 / 9
• Subtask 6: 0 / 30
• Subtask 7: 0 / 24