Submission #1126444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126444		Wendidiask	Coin Collecting (JOI19_ho_t4)	C++20	100 / 100	138 ms	2764 KiB

joi2019_ho_t4

/*
                                     :---:--:--::::::--:-:----:                                     
                               ::-:::.                         ::-:::                               
                       .*  -===..                                    :---                           
                     .-+*##=-------====-:                                :--:                       
                  :+##=.* -=            :=+-                                .-=:                    
               .+++-.  :-   -=.            .=+-                                .--.                 
             .++=-     +      -=              :*-                                 :-.               
            +*+-      :-        -=.             -*:                                 :=:             
           #*:        *           -=.             +-                                  .=            
        =:%+         -:             -=.            +-                                   --          
        -%:          *                -=.           *:                                    +.        
       :%-..        =.                  -=.          #                                     -:       
      :=#   ..      +                     -=.        ==                                     -=      
     ---+     .    =                        -=.      .#                                      .+     
    -: ==       .  =         :------::------:.-=.     %                                       .=    
   :-  ==        .=.     ---:.               :--#+.  .%                                        :-   
   =   .*        .+.. :=-                        :++ -+                                         =:  
  +     #.       +  -=:                            :*%-*:                                        *  
 :=     :#      :=:=   .                    :-----: =+-+                                         .+ 
 *       -*     *=-     . .-        :::::::.       :*  .#+.                                       + 
:-        -+   :#.        --::-----:              :*     ++=                                      .-
+          :*. *.    .:::::*%:                   ++       +.-=.                                    +
+           -#**----:       .=                 -*.         +  -=                                   =
*           +.#=+:           +  .           .=+:           =.   -=.                                =
=            -+  :++:         +   ..     .=+=              .=     -=.                              -
=            %-     :====-:.  =.  .:--===-                  *       -=.                            -
+           +--          .:--==#==-:.=                      +         -=.                          =
*           + *                =.    :                     .=           -=.                        =
+          =  *                 +                          =              -=.                      +
:-         =  .=                =:                         =                -=.                   .-
 *        +    =:                *                        *                   -=.                 + 
 :-      .+     =-               :-                     .+                      -=.              .+ 
  *      *       :=               *                    :=                         -=             *  
   =    :-         =:             .-                 .=:                            -=.         =:  
   -:   *           .=-            +               .=-                                -=       :-   
    =: -:              --:         :-           :--:                                    -=.   .=    
     =:+                  ----.     *       :---.                                         -= .+     
    --=*----------------------=*+=--=+--=+*+------------------------------------------------%+:.    
    :: :=                           +:-                                                    -- :.    
        .=.                                                                               =.        
          -=                                                                            -=          
           .=:                                                                        .=.           
             .=:                                                                    .+:             
               :--                                                                :-:               
                  --                                                            -=.                 
                    :--.                                                     --:                    
                       :--:                                              .--:                       
                          .-:-:                                      ::--.                          
                               :----.                          .:----                               
                                    .:::::::::-::::::--::::::::.                             
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cerr << #x << " is " << x << "\n"
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define linebreak cout << "---------------------------------------------------------\n"
#define f first
#define s second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// good luck
const int MS = 1e5+5, mod = 1e9+9, INF = 3e18, blk = 400;
int n, ans = 0, a[MS][3]; 
int32_t main() {
	cin >> n;
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= 2*n; i++) {
		int x, y; cin >> x >> y;
		if (1 <= x and x <= n and 1 <= y and y <= 2) {
			a[x][y]++;
		}
		if (x > n and y > 2) {
			ans += abs(x-n)+abs(y-2);
			a[n][2]++;
		}
		if (x > n and y < 1) {
			ans += abs(x-n)+abs(y-1);
			a[n][1]++;
		}
		if (x < 1 and y > 2) {
			ans += abs(x-1)+abs(y-2);
			a[1][2]++;
		}
		if (x < 1 and y < 1) {
			ans += abs(x-1)+abs(y-1);
			a[1][1]++;
		}
		if (1 <= x and x <= n and y > 2) {
			ans += abs(y-2);
			a[x][2]++;
		}
		if (1 <= x and x <= n and y < 1) {
			ans += abs(y-1);
			a[x][1]++;
		}
		if (1 <= y and y <= 2 and x > n) {
			ans += abs(x-n);
			a[n][y]++;
		}
		if (1 <= y and y <= 2 and x < 1) {
			ans += abs(x-1);
			a[1][y]++;
		}
	}
	/*for (int j = 1; j <= 2; j++) {
		for (int i = 1; i <= n; i++) cout << a[i][j] << ' ';
		cout << '\n';
	}*/
	int top = 0, bot = 0;
	for (int i = 1; i <= n; i++) {
		top += a[i][1]-1;
		bot += a[i][2]-1;
		if (top >= 0 and bot < 0) {
			int temp = min(top, -bot);
			ans += temp;
			top -= temp;
			bot += temp;
		}
		if (top < 0 and bot >= 0) {
			int temp = min(-top, bot);
			ans += temp;
			top += temp;
			bot -= temp;
		}
		ans += abs(top)+abs(bot);
	}
	cout << ans;
}

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