Submission #165337

#	Time	Username	Problem	Language	Result	Execution time	Memory
165337		Akashi	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	98 ms	7460 KiB

joi2019_ho_t4

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

struct coins{
    int x, y;
    bool operator < (const coins &aux)const{
        if(x != aux.x) return x < aux.x;
        return y < aux.y;
    }
};

coins a[200005];

int n;
queue <int> coins[3], cell[3];

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);

    long long Sol = 0;
    for(int i = 1; i <= 2 * n ; ++i){
        scanf("%d%d", &a[i].x, &a[i].y);

        if(a[i].x < 1) Sol = Sol + (1 - a[i].x), a[i].x = 1;
        if(a[i].x > n) Sol = Sol + (a[i].x - n), a[i].x = n;

        if(a[i].y < 1) Sol = Sol + (1 - a[i].y), a[i].y = 1;
        if(a[i].y > 2) Sol = Sol + (a[i].y - 2), a[i].y = 2;
    }

    sort(a + 1, a + 2 * n + 1);

    int j = 1;
    for(int i = 1; i <= n ; ++i){
        while(a[j].x <= i && j <= 2 * n) coins[a[j].y].push(a[j].x), ++j;


        cell[1].push(i);
        cell[2].push(i);

        while(!cell[1].empty() && !coins[1].empty()){
            Sol = Sol + abs(cell[1].front() - coins[1].front());
            cell[1].pop();
            coins[1].pop();
        }
        ///
        while(!cell[2].empty() && !coins[2].empty()){
            Sol = Sol + abs(cell[2].front() - coins[2].front());
            cell[2].pop();
            coins[2].pop();
        }
        ///
        while(!cell[1].empty() && !coins[2].empty()){
            Sol = Sol + abs(cell[1].front() - coins[2].front()) + 1;
            cell[1].pop();
            coins[2].pop();
        }
        ///
        while(!cell[2].empty() && !coins[1].empty()){
            Sol = Sol + abs(cell[2].front() - coins[1].front()) + 1;
            cell[2].pop();
            coins[1].pop();
        }
    }

    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].x, &a[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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