oj.uz

Submission #461283

# Submission time Handle Problem Language Result Execution time Memory
461283 2021-08-09T16:38:11 Z TeaTime Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 204 KB 
//#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -