oj.uz

Submission #634551

# Submission time Handle Problem Language Result Execution time Memory
634551 2022-08-24T14:48:43 Z slime Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 0 ms 212 KB 
#include "bits/stdc++.h"
#define int long long
using namespace std;

struct coin {
    int ox, oy; // original x, y
    int nx, ny; // new x, y
    int cost = 0;
};
void solve(int tc) {
    int n;
    cin >> n;
    coin c[2*n + 1];
    for(int i=1; i<=2*n; i++) {
        cin >> c[i].ox >> c[i].oy;
        if(c[i].ox > n) {
            if(c[i].oy >= 2) { // Choose (n, 2)
                c[i].nx = n;
                c[i].ny = 2;
            }
            else { // Choose (n, 1)
                c[i].nx = n;
                c[i].ny = 1;
            }
        }
        else if(c[i].ox < 1) {
            if(c[i].oy >= 2) {
                c[i].nx = 1;
                c[i].ny = 2;
            }
            else {
                c[i].nx = 1;
                c[i].ny = 1;
            }
        }
        else { 
            if(c[i].oy >= 2) {
                c[i].nx = c[i].ox;
                c[i].ny = 2;
            }
            else {
                c[i].nx = c[i].ox;
                c[i].ny = 1;
            }
        }

        c[i].cost = abs(c[i].ox - c[i].nx) + abs(c[i].oy - c[i].ny);
    }
    int base = 0;
    for(int i=1; i<=2*n; i++) base += c[i].cost;
    int cnt[n+1][3];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=2; j++) {
            cnt[i][j] = 0;
        }
    }

    for(int i=1; i<=2*n; i++) cnt[c[i].nx][c[i].ny]++;

    for(int i=1; i<=2*n; i++) {
        int jj = -1, kk = -1;
        bool done = 0;
        for(int j=1; j<=2; j++) {
            for(int k=1; k<=n; k++) {
                if(cnt[k][j] > 1) {
                    kk = k, jj = j;
                    done = 1;
                    break;
                }
            }
            if(done) break;
        }
        done = 0;
        if(jj == -1) break;
        for(int j=1; j<=2; j++) {
            for(int k=1; k<=n; k++) {
                if(cnt[k][j] == 0) {
                    base += abs(j - jj) + abs(k - kk);
                    cnt[kk][jj]--;
                    cnt[k][j]++;
                    done = 1;
                    break;
                }
            }
            if(done) break;
        }
    }
    cout << base << '\n';

}
int32_t main() {
    int t = 1;
    // cin >> t;
    for(int i=1; i<=t; i++) solve(i);
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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