Submission #234548

#	Time	Username	Problem	Language	Result	Execution time	Memory
234548		nicolaalexandra	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	294 ms	10224 KiB

joi2019_ho_t4

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

pair <long long, long long> v[DIM];
vector <int> coins[3],libere[3];
long long a[DIM][3], sol;
int n,i,j;

inline long long modul (long long n){
    if (n < 0)
        return -n;
    return n;
}
long long dist (long long x, long long y, long long x2, long long y2){
    return modul (x - x2) + modul (y - y2);
}
int main (){
  
    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=2*n;i++){
        cin>>v[i].first>>v[i].second;
        if (v[i].first < 1 && v[i].second > 2){
            a[1][2]++;
            sol += dist (v[i].first,v[i].second,1,2);
            continue;
        }

        if (v[i].first >= 1 && v[i].first <= n && v[i].second > 2){
            a[v[i].first][2]++;
            sol += dist (v[i].first,v[i].second,v[i].first,2);
            continue;
        }

        if (v[i].first > n && v[i].second > 2){
            a[n][2]++;
            sol += dist (v[i].first,v[i].second,n,2);
            continue;
        }

        if (v[i].first > n && v[i].second >= 1 && v[i].second <= 2){
            a[n][v[i].second]++;
            sol += dist (v[i].first,v[i].second,n,v[i].second);
            continue;
        }

        if (v[i].first > n && v[i].second < 1){
            a[n][1]++;
            sol += dist (v[i].first,v[i].second,n,1);
            continue;
        }

        if (v[i].first >= 1 && v[i].second <= n && v[i].second < 1){
            a[v[i].first][1]++;
            sol += dist (v[i].first,v[i].second,v[i].first,1);
            continue;
        }

        if (v[i].first < 1 && v[i].second < 1){
            a[1][1]++;
            sol += dist (v[i].first, v[i].second,1,1);
            continue;
        }

        if (v[i].first < 1 && v[i].second >= 1 && v[i].second <= 2){
            a[1][v[i].second]++;
            sol += dist (v[i].first,v[i].second,1,v[i].second);
            continue;
        }
        a[v[i].first][v[i].second]++;
    }

    for (i=1;i<=n;i++){
        if (!a[i][1])
            libere[1].push_back(i);
        if (!a[i][2])
            libere[2].push_back(i);

        while (a[i][1] > 1){
            coins[1].push_back (i);
            a[i][1]--;
        }

        while (a[i][2] > 1){
            coins[2].push_back(i);
            a[i][2]--;
        }

        /// pun banii de pe prima linie in pozitiile libere tot de pe prima linie
        while (!coins[1].empty() && !libere[1].empty()){
            int poz1 = coins[1].back(), poz2 = libere[1].back();
            sol += modul (poz1 - poz2);
            coins[1].pop_back(), libere[1].pop_back();
        }

        /// la fel si pt linia a doua
        while (!coins[2].empty() && !libere[2].empty()){
            int poz1 = coins[2].back(), poz2 = libere[2].back();
            sol += modul (poz1 - poz2);
            coins[2].pop_back(), libere[2].pop_back();
        }

        /// acum mut de pe prima pe a doua si invers

        while (!coins[1].empty() && !libere[2].empty()){
            int poz1 = coins[1].back(), poz2 = libere[2].back();
            sol += modul(poz1 - poz2) + 1;
            coins[1].pop_back(), libere[2].pop_back();
        }

        while (!coins[2].empty() && !libere[1].empty()){
            int poz1 = coins[2].back(), poz2 = libere[1].back();
            sol += modul (poz1 - poz2) + 1;
            coins[2].pop_back(), libere[1].pop_back();
        }
    }


    /*
    int poz1 = 1, poz2 = 1;
    for (i=1;i<=n;i++){

        /// incerc sa le duc cat mai mult in stanga
        while (a[i][1] > 1){
            while (poz1 < i && a[poz1][1])
                poz1++;

            if (poz1 < i){
                sol += i - poz1;
                a[i][1]--;
                a[poz1][1] = 1;
            } else break;
        }

        while (a[i][2] > 1){
            while (poz1 < i && a[poz2][2])
                poz2++;
            if (poz2 < i){
                sol += i - poz2;
                a[i][2]--;
                a[poz2][2] = 1;
            } else break;
        }

        /// mut moneda de pe prima linie pe a doua si invers
        while (a[i][1] > 1){
            while (poz2 <= i && a[poz2][2])
                poz2++;
            if (poz2 <= i){
                sol += i - poz2 + 1;
                a[i][1]--;
                a[poz2][2] = 1;
            } else break;
        }

        while (a[i][2] > 1){
            while (poz1 <= i && a[poz1][1])
                poz1++;
            if (poz1 <= i){
                sol += i - poz1 + 1;
                a[i][2]--;
                a[poz1][1] = 1;
            } else break;
        }
    }

    /// acum duc spre dreapta monedele
    poz1 = n, poz2 = n;

    for (i=1;i<=n;i++){
        while (a[i][1] > 1){
            while (poz1 > i && a[poz1][1])
                poz1--;
            if (poz1 > i){
                sol += poz1 - i;
                a[i][1]--;
                a[poz1][1] = 1;
            } else break;
        }

        while (a[i][2] > 1){
            while (poz2 > i && a[poz2][2])
                poz2--;
            if (poz2 > i){
                sol += poz2 - i;
                a[i][2]--;
                a[poz2][2] = 1;
            } else break;
        }

        while (a[i][1] > 1){
            while (poz2 >= i && a[poz2][2])
                poz2--;
            if (poz2 >= i){
                sol += poz2 - i + 1;
                a[i][1]--;
                a[poz2][2] = 1;
            } else break;
        }

        while (a[i][2] > 1){
            while (poz1 >= i && a[poz1][1])
                poz1--;
            if (poz1 >= i){
                sol += poz1 - i + 1;
                a[i][2]--;
                a[poz1][1] = 1;
            } else break;
        }
    }
*/
    cout<<sol;

    return 0;
}

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