oj.uz

Submission #902541

# Submission time Handle Problem Language Result Execution time Memory
902541 2024-01-10T15:46:18 Z jay_jayjay Coin Collecting (JOI19_ho_t4) C++17
0 / 100
 1 ms 348 KB 
// {{{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);


        sort(all(coins));

        ll tot=0;
        for(auto&[x,y]:coins) {
                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;
        }

        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]--;

        //printf("%lld\n",tot);
        //for(int y=0;y<2;y++) {
                //for(int x=0;x<n;x++) {
                        //printf("%d ",f[y][x]);
                //}
                //printf("\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;
                        tot += 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;
                }

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

Compilation message

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
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 63.0

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