Submission #461283

#	Time	Username	Problem	Language	Result	Execution time	Memory
461283		TeaTime	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	204 KiB

joi2019_ho_t4

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 3050;

char grid[SZ][SZ];

vector<pair<ll, ll>> vec;
int main() {
    fastInp;

    ll n;
    cin >> n;
    n *= 2;

    vec.resize(n);
    for (auto& c : vec) cin >> c.first >> c.second;

    random_shuffle(vec.begin(), vec.end());
    ll cur = 0;
    for (int i = 0; i < n; i++) {
        pair<ll, ll> p2 = { i % (n / 2), i / (n / 2) };
        p2.first++;
        p2.second++;
        cur += abs(p2.first - vec[i].first) + abs(p2.second - vec[i].second);
    }

    for (int t = 0; t < n; t++) {
        for (int i = 0; i < n; i++) {
            pair<ll, ll> p = { i % (n / 2), i / (n / 2) };
            p.first++;
            p.second++;
            for (int j = i + 1; j < n; j++) {
                pair<ll, ll> p2 = { j % (n / 2), j / (n / 2) };
                p2.first++;
                p2.second++;
                ll oldcnt = abs(p2.first - vec[j].first) + abs(p2.second - vec[j].second) + abs(p.first - vec[i].first) + abs(p.second - vec[i].second);
                ll nwcnt = abs(p.first - vec[j].first) + abs(p.second - vec[j].second) + abs(p2.first - vec[i].first) + abs(p2.second - vec[i].second);
                if (nwcnt < oldcnt) {
                    swap(vec[j], vec[i]);
                    cur -= (oldcnt - nwcnt);
                }
            }
        }
    }

    cout << cur;

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63