Submission #125509

#	Time	Username	Problem	Language	Result	Execution time	Memory
125509		wilwxk	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	2 ms	376 KiB

joi2019_ho_t4

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

const int MAXN=2e3+5;
const ll INF=1e15+9;
vector<pair<ll, ll> > v[2];
int n;
ll respf;

ll dist(int a, int b, ll x) {
	if(b>=v[a].size()) return INF;
	ll resp=0;
	auto ponto=v[a][b];
	resp+=abs(ponto.first-x);
	resp+=min(abs(ponto.second-2), abs(ponto.second-1));
	return resp;
}

int main() {
	scanf("%d", &n); n*=2;
	for(int i=1; i<=n; i++) {
		int a, b; scanf("%d %d", &a, &b);
		if(b>=2) {
			respf+=llabs(b-2); b=2;
			v[0].push_back({a, b});
		}
		else {
			respf+=llabs(b-1); b=1;
			v[1].push_back({a, b});
		}
	}
	sort(v[0].begin(), v[0].end());
	sort(v[1].begin(), v[1].end());

	int a=0; int b=0;
	for(int i=1; i<=n/2; i++) {
		int ind=i;
		ll val= a>=v[0].size() ? INF : v[0][a].first-ind;
		ll val2= b>=v[1].size() ? INF : v[1][b].first-ind;
		if(val<=val2) {
			respf+=dist(0, a, i);
			ll val3= a+1>=v[0].size() ? INF : v[0][a+1].first;
			if(val3<val2) respf+=dist(0, a+1, i)+1, a+=2;
			else respf+=dist(1, b, i), a++, b++;
		}
		else {
			ll val3= b+1>=v[1].size() ? INF : v[1][b+1].first;
			respf+=dist(1, b, i);
			if(val3<val) respf+=dist(1, b+1, i)+1, b+=2;
			else respf+=dist(0, a, i), a++, b++;
		}
		// printf("calc %d %d %d\n", ind, a, b);
	}

	printf("%lld\n", respf);
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'll dist(int, int, ll)':
joi2019_ho_t4.cpp:12:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(b>=v[a].size()) return INF;
     ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   ll val= a>=v[0].size() ? INF : v[0][a].first-ind;
           ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:40:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   ll val2= b>=v[1].size() ? INF : v[1][b].first-ind;
            ~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    ll val3= a+1>=v[0].size() ? INF : v[0][a+1].first;
             ~~~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    ll val3= b+1>=v[1].size() ? INF : v[1][b+1].first;
             ~~~^~~~~~~~~~~~~
joi2019_ho_t4.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); n*=2;
  ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

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