oj.uz

Submission #226325

# Submission time Handle Problem Language Result Execution time Memory
226325 2020-04-23T11:17:41 Z Ruxandra985 Coin Collecting (JOI19_ho_t4) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
pair <long long,long long> v[200010];
long long f[200010][3] , taken[100010][3];

long long modul (long long x){
    return max(x , -x);
}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long i , n , l1 , c1 , l2 , c2 , part , aux;
    long long sol = 0;
    fscanf (fin,"%lld",&n);
    for (i = 1 ; i <= 2 * n ; i++){
        fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);

        /// acum reduci v ul

        if (v[i].second <= 1){

            sol = sol + 1 - v[i].second;
            v[i].second = 1;

        }
        else {

            sol = sol + v[i].second - 2;
            v[i].second = 2;

        }

        if (v[i].first < 1){

            sol = sol + 1 - v[i].first;
            v[i].first = 1;

        }
        else if (v[i].first > n){

            sol = sol + v[i].first - n;
            v[i].first = n;

        }

        f[v[i].first][v[i].second]++;

        //printf ("%lld %lld\n", v[i].first , v[i].second);


    }
    /// renunt la heap gata ok am inteles, nu e bn:)))))

    for (i = 1 ; i <= n ; i++){
        if (f[i][1] > 0){
            taken[i][1] = 1;
            f[i][1]--;
        }

        if (f[i][2] > 0){
            taken[i][2] = 1;
            f[i][2]--;
        }
    }

    c1 = c2 = 0;
    l1 = l2 = 0;
    aux = sol;
    sol = 0;

    for (i = 1 ; i <= n ; i++){

        //if (i == 3)
          //  printf ("a");

        if (!c1){
            /// te duci in sus pana gasesti cv
            l1++;

            while (l1 <= n && !f[l1][1])
                l1++;

            if (l1 <= n)
                c1 = f[l1][1];

        }

        if (!c2){
            /// te duci in sus pana gasesti cv
            l2++;

            while (l2 <= n && !f[l2][2])
                l2++;

            if (l2 <= n)
                c2 = f[l2][2];

        }

        if (!taken[i][1]){

            if ( min(l2 , l1) <= i ){

                if (l2 < l1){
                    c2--;
                    sol += modul(l2 - i) + 1;
                }
                else {
                    c1--;
                    sol += modul(l1 - i);
                }

            }
            else if ((c1 && c2 && modul(l1 - i) <= modul(l2 - i) + 1) || !c2){
                c1--;
                sol += modul(l1 - i);
            }
            else {
                c2--;
                sol += modul(l2 - i) + 1;
            }

        }

        if (!taken[i][2]){

            if ( min(l2 , l1) <= i ){

                if (l2 <= l1){
                    c2--;
                    sol += modul(l2 - i);
                }
                else {
                    c1--;
                    sol += modul(l1 - i) + 1;
                }

            }
            else if ((c1 && c2 && modul(l2 - i) <= modul(l1 - i) + 1) || !c1){
                c2--;
                sol += modul(l2 - i);
            }
            else {
                c1--;
                sol += modul(l1 - i) + 1;
            }

        }


    }

    c1 = c2 = 0;
    l1 = l2 = 0;
    part = sol;
    sol = 0;

    for (i = 1 ; i <= n ; i++){

        if (!c1){
            /// te duci in sus pana gasesti cv
            l1++;

            while (l1 <= n && !f[l1][1])
                l1++;

            if (l1 <= n)
                c1 = f[l1][1];

        }

        if (!c2){
            /// te duci in sus pana gasesti cv
            l2++;

            while (l2 <= n && !f[l2][2])
                l2++;

            if (l2 <= n)
                c2 = f[l2][2];

        }

        if (!taken[i][1]){

            if ((c1 && c2 && modul(l1 - i) <= modul(l2 - i) + 1) || !c2){
                c1--;
                sol += modul(l1 - i);
            }
            else {
                c2--;
                sol += modul(l2 - i) + 1;
            }

        }

        if (!taken[i][2]){

            if ((c1 && c2 && modul(l2 - i) <= modul(l1 - i) + 1) || !c1){
                c2--;
                sol += modul(l2 - i);
            }
            else {
                c1--;
                sol += modul(l1 - i) + 1;
            }

        }


    }

    part = min(part , sol);

    fprintf (fout,"%lld",aux + part);

    return 0;
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:17:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld",&n);
     ~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t4.cpp:19:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld%lld",&v[i].first,&v[i].second);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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