Submission #902552

#	Time	Username	Problem	Language	Result	Execution time	Memory
902552		jay_jayjay	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	54 ms	7752 KiB

joi2019_ho_t4

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
// 1}}}

void chmin(ll& x, ll y) { x=min(x,y); }

int dist(array<int,2> a, array<int,2> b) { return abs(a[0]-b[0])+abs(a[1]-b[1]); }

int main()
{
        int n;scanf("%d",&n);

        vector<array<int,2>> coins(2*n);
        for(auto&[x,y]:coins)scanf("%d%d",&x,&y);

        ll tot=0;
        for(auto&[x,y]:coins) {
                //printf("%d, %d -> ",x,y);
                if(y < 1) tot += 1-y, y=1;
                if(y > 2) tot += y-2, y=2;

                if(x < 1) tot += 1-x, x=1;
                if(x > n) tot += x-n, x=n;
                //printf("%d, %d\n",x,y);
        }

        vector f(2, vector<int>(n));

        for(auto&[x,y]:coins) f[y-1][x-1]++;
        for(int y=0;y<2;y++)
                for(int x=0;x<n;x++) f[y][x]--;

        //dprintf("%lld\n",tot);
        //for(int y=0;y<2;y++) {
                //for(int x=0;x<n;x++) {
                        //dprintf("%d ",f[y][x]);
                //}
                //dprintf("\n");
        //}
        // moving a (1/-1) incurs 1 cost
        for(int x=0;x<n-1;x++) {
                if(f[0][x] < 0 && f[1][x] > 0) {
                        int del = f[0][x]+f[1][x];
                        if(del<=0)tot+=f[1][x],f[0][x]=del,f[1][x]=0;
                        else tot+=-f[0][x],f[0][x]=0,f[1][x]=del;
                }
                if(f[0][x] > 0 && f[1][x] < 0) {
                        int del = f[0][x]+f[1][x];
                        if(del<=0)tot+=f[0][x],f[0][x]=0,f[1][x]=del;
                        else tot+=-f[1][x],f[0][x]=del,f[1][x]=0;
                }

                //dprintf("x=%d: %lld\n",x,tot);
                tot += abs(f[0][x])+abs(f[1][x]);
                f[0][x+1] += f[0][x];
                f[1][x+1] += f[1][x];
                f[0][x]=f[1][x]=0;
                //dprintf("x=%d: %lld\n",x,tot);
                //for(int y=0;y<2;y++) {
                        //for(int x=0;x<n;x++) {
                                //dprintf("%d ",f[y][x]);
                        //}
                        //dprintf("\n");
                //}
        }
        tot += abs(f[0][n-1]);
        printf("%lld\n",tot);
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:26:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         int n;scanf("%d",&n);
      |               ~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:29:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         for(auto&[x,y]:coins)scanf("%d%d",&x,&y);
      |                              ~~~~~^~~~~~~~~~~~~~

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