Submission #899585

#	Time	Username	Problem	Language	Result	Execution time	Memory
899585		sunwukong123	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	1 ms	2444 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 100005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int A[MAXN][3];
bool done[MAXN][3];
int ans;

int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=1;i<=2*n;i++){
		int x,y;cin>>x>>y;
		int nx,ny;
		if(y>=2)ny=2;
		else ny=1;

		if(x<=1)nx=1;
		else if(x<=n)nx=x;
		else nx=n;
		ans+=abs(x-nx) + abs(y-ny);
		A[nx][ny]++;
	}
	for(int i=1;i<=n;i++){
		debug(A[i][1],A[i][2]);
	}
	for(int i=1;i<=n;i++){
		debug(i);
		if(A[i][1] + A[i][2] >= 2){
			if(A[i][1]){
				--A[i][1];
			} else{
				--A[i][2];
				++ans;
			}

			if(A[i][2]){
				--A[i][2];
			} else{
				--A[i][1];
				++ans;
			}
			A[i+1][1] += A[i][1];
			ans+=A[i][1];
			A[i+1][2] += A[i][2];
			ans+=A[i][2];
		} else{
			int sum=0;
			int lst=i;
			bool found=0;
			for(int j=i;j<=n;j++){
				sum+=A[j][1];
				sum+=A[j][2];
				sum-=2;
				debug(j,sum);
				if(sum>=0){
					found=1;
					lst=j;
					break;
				}
			}
			assert(found==1);
			//go from j to i instead; just refund unused things
			int c1=0,c2=0;
			for(int j=lst;j>=i;j--){
				c1 += A[j][1];
				c2 += A[j][2];

				//assert(c1+c2>=2);
				if(c1){
					--c1;
				} else {
					--c2;
					++ans;
				}

				if(c2){
					--c2;
				} else {
					--c1;
					++ans;
				}
				if(j!=i){
					ans += c1 + c2; // move them to j-1;
				} else{
					ans -= (c1+c2)*(lst-i);
				}
			}
			A[lst+1][1]+=c1;
			A[lst+1][2]+=c2;
			ans+=c1;
			ans+=c2;
			i=lst;
		}
	}
	cout<<ans;
}	

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