oj.uz

Submission #133301

# Submission time Handle Problem Language Result Execution time Memory
133301 2019-07-20T11:32:43 Z osaaateiasavtnl Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 2 ms 376 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
map <int, vector <int> > d;
int get(vector <int> a, int c1, int c2) {
    int ans = 0;
    int up = 0, down = 0;
    for (int x : a) {
        if (x >= 2) {
            ++up;
            ans += x - 2;
        }   
        else {
            ++down;
            ans += 1 - x;
        }   
    }   
    return ans + abs(c1 - down);
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < 2 * n; ++i) {
        int x, y;
        cin >> x >> y;
        d[x].push_back(y);
    }   
    vector <int> vx;
    for (int i = 1; i <= n; ++i) {
        vx.push_back(i);
        vx.push_back(i);
    }   
    int c = 0;
    int ans = 0, ans1 = 0, ans2 = 0;
    int ptr = 0;
    for (auto e : d) {
        int x = e.first;
        auto a = e.second;
        int add = 0;
        for (int i = 0; i < a.size(); ++i) {
            add += abs(vx[ptr] - x);                
            ++ptr;
        }   
        if (c & 1) {
            if ((c + a.size()) & 1) {
                int t = a.size() / 2 - 1;
                ans1 = min(ans1 + get(a, t + 1, t + 1), ans2 + get(a, t + 2, t)) + add;
                ans2 = min(ans1 + get(a, t, t + 2), ans2 + get(a, t + 1, t + 1)) + add;
            }
            else {
                int t = a.size() / 2;
                ans = min(ans1 + get(a, t, t + 1), ans2 + get(a, t + 1, t)) + add;
            }   
        }
        else {
            if ((int)a.size() & 1) {
                int t = a.size() / 2;
                ans1 = ans + get(a, t + 1, t) + add;
                ans2 = ans + get(a, t, t + 1) + add;
            }
            else {
                int t = a.size() / 2;
                ans = ans + get(a, t, t) + add;
            }   
        }
        c += a.size();
    }   
    cout << ans << '\n';
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a.size(); ++i) {
                         ~~^~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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