Submission #923219

#	Time	Username	Problem	Language	Result	Execution time	Memory
923219		HorizonWest	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	47 ms	10524 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(998244353)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e6 + 7, Inf = 1e15 + 7;

void print(bool x) { cout << (x ? "Yes" : "No") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

int Z(int x) 
{
    return (x * (x + 1)) / 2;
}

void solve()
{
    int n, ans = 0; cin >> n;
    vector <vector<int>> v(n + 1, vector <int> (3, 0));
    for(int i = 0; i < 2 * n; i++)
    {
        int x, y; cin >> x >> y;
        if(x < 1)
        {
            ans += abs(1 - x);
            x = 1;
        }

        if(x > n)
        {
            ans += abs(n - x);
            x = n;
        }

        if(y < 1)
        {
            ans += abs(1 - y);
            y = 1;
        }

        if(y > 2)
        {
            ans += abs(2 - y);
            y = 2;
        }

        v[x][y]++;
    }

    /*for(int j = 2; j >= 1; j--) 
    {
        for(int i = 1; i <= n; i++)
            cerr << v[i][j] << " ";
        cerr << endl;
    }
    cerr << ans << endl;*/

    int a = 0, b = 0;

    for(int i = 1; i <= n; i++)
    {
        ans += v[i-1][1] + v[i-1][2];
        v[i][1] += v[i-1][1];
        v[i][2] += v[i-1][2];

        a++; b++;

        if(v[i][1] > 0)
        {   
            while(min(a, v[i][1]) != 0)
            {
                ans += a - 1; a--;
                v[i][1]--;
            }
        }

        if(v[i][2] > 0)
        {
            while(min(b, v[i][2]) != 0)
            {
                ans += b - 1; b--;
                v[i][2]--;
            }
        }

        if(v[i][1] > 0)
        {
            while(min(b, v[i][1]) != 0)
            {
                ans += b; b--;
                v[i][1]--;
            }
        }

        if(v[i][2] > 0)
        {
            while(min(a, v[i][2]) != 0)
            {
                ans += a; a--;
                v[i][2]--;
            }
        }
    }

    cout << ans << endl;
}

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

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

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