Submission #762300

# Submission time Handle Problem Language Result Execution time Memory
762300 2023-06-21T09:27:03 Z sysia Coin Collecting (JOI19_ho_t4) C++17
0 / 100
1 ms 340 KB
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct Tree{
    vector<int>tab;
    int size = 1;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
    }

    void update(int x, int v){
        x += size;
        tab[x] += v;
        while (x){
            x/=2;
            tab[x] = tab[2*x] + tab[2*x+1];
        }
    }

    int query(int l, int r){
        int ans = 0;
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) ans += tab[l+1];
            if (r&1) ans += tab[r-1];
        }
        return ans;
    }
};

void solve(){
    int n; cin >> n;
    int N = 2*n;
    int ans = 0;
    vector<T>a(N);
    vector cnt(n+2, vector<int>(3));
    for (auto &[x, y] : a){
        cin >> x >> y;
        if (x < 1) {
            ans += (1-x);
            x = 1;
        } 
        if (x > n){
            ans += (x - n);
            x = n;
        }
        if (y < 1){
            ans += (1 - y);
            y = 1;
        }
        if (y > 2){
            ans += (y - 2);
            y = 2;
        }
        cnt[x][y-1]++;
    }
    debug(ans);
    // for (int j = 1; j>=0; j--){
    //     for (int i = 1; i<=n; i++){
    //         cerr << cnt[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    vector<int>leave(2);
    for (int what = 0; what < 2; what++){
        vector<int>ord;
        if (!what) {
            for (int i = 1; i<=n; i++) ord.emplace_back(i);
        } else {
            for (int i = n; i>=1; i--) ord.emplace_back(i);
        }
        for (auto i: ord){
            debug(i, ans, cnt[i][0], cnt[i][1]);
            int d = cnt[i][0] + cnt[i][1];
            if (d < 2){                
                //musimy znalezc cos zeby przyciagnac
                for (int rep = 0; rep < 2; rep++){
                    if (!cnt[i][rep]){
                        leave[rep]++;
                    }
                }
                continue;
            }
            //d >= 2 
            
            vector<int>mv(2);
            for (int rep = 0; rep < 2; rep++){
                int t = min(leave[rep], max(0ll, cnt[i][rep]-1)); //t zostaje w miejscu, przesuwamy je pozniej w lewo na tym samym lvl
                leave[rep] -= t;
                ans += t;
                cnt[i-1][rep] += t;
                cnt[i][rep] -= t;
                mv[rep] = max(0ll, cnt[i][rep]-1);
            }
            debug(cnt[i][0], cnt[i][1]);
            debug(mv);
            for (int rep = 0; rep < 2; rep++){
                if (leave[rep]){
                    int t = min(mv[rep^1], leave[rep]);
                    //tyle mozemy ukrasc i przesunac w pionie, by potem miec na lewo
                    ans += 2*t;
                    cnt[i-1][rep] += t;
                    cnt[i][rep^1] -= t;
                    leave[rep] -= t;
                }
            }
            d = cnt[i][0] + cnt[i][1];
            if (d < 2){
                for (int rep = 0; rep < 2; rep++){
                    if (!cnt[i][rep]){
                        leave[rep]++;
                    }
                }
                continue;
            }
            for (int rep = 0; rep < 2; rep++){
                if (!cnt[i][rep] && mv[rep^1]){
                    ans++;
                    cnt[i][rep]++;
                    cnt[i][rep^1]--;
                }
            }
            for (int rep = 0; rep < 2; rep++){
                cnt[i+1][rep] += (cnt[i][rep]-1);
                ans += (cnt[i][rep]-1);
                cnt[i][rep] = 1;
            }
            debug(cnt[i][0], cnt[i][1]);
        }
        // for (int j = 1; j>=0; j--){
        //     for (int i = 1; i<=n; i++){
        //         cerr << cnt[i][j] << " ";
        //     }
        //     cerr << "\n";
        // }
        debug(ans);
        // return;
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 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 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -
# 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 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -
# 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 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -