oj.uz

답안 #130877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130877 2019-07-16T08:00:19 Z 임유진(#3171) Bodyguards (CEOI10_bodyguards) C++14
0 / 100
 116 ms 8412 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXR 200005
#define fi first
#define se second

typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;

vector<pll> rv, cv;

int main() {
	int R, C;

	scanf("%d", &R);
	rv.resize(R);
	for(int i = 0; i < R; i++) scanf("%lld%lld", &rv[i].fi, &rv[i].se);
	scanf("%d", &C);
	cv.resize(C);
	for(int i = 0; i < C; i++) scanf("%lld%lld", &cv[i].fi, &cv[i].se);

	lint sumr = 0, sumc = 0;
	for(int i = 0; i < R; i++) sumr += rv[i].fi * rv[i].se;
	for(int i = 0; i < C; i++) sumc += cv[i].fi * cv[i].se;
	if(sumr != sumc) {
		printf("0");
		return 0;
	}

	cv.push_back(make_pair(0ll, 1ll << 60));
	sort(rv.begin(), rv.end());
	sort(cv.begin(), cv.end());

	vector<pll> v;
	for(int i = 0; i < cv.size(); i++) {
		if(i > 0 && cv[i - 1].fi == cv[i].fi) v.back().se += cv[i].se;
		else v.push_back(cv[i]);
	}
	swap(cv, v);


	for(auto a : rv) {
		//printf("cv : ");
		//for(auto a : cv) printf("(%lld, %lld)", a.fi, a.se);
		//printf("\n");
		if(cv[cv.size() - 2].se < a.fi || (cv.back().fi > cv[cv.size() - 2].fi + 1 && cv.back().se < a.fi)) {
			printf("0");
			return 0;
		}
		lint left = a.fi * a.se;
		//printf("a = (%lld, %lld), left = %lld\n", a.fi, a.se, left);
		while(left > 0) {
			if(left >= cv.back().se * (cv.back().fi - cv[cv.size() - 2].fi)) {
				cv[cv.size() - 2].se += cv.back().se;
				left -= cv.back().se * (cv.back().fi - cv[cv.size() - 2].fi);
				cv.pop_back();
			}
			else {
				pll p = cv.back();
				cv.back().fi -= (left - 1) / p.se + 1;
				cv.back().se = (left - 1) % p.se + 1;
				if(cv.back().fi == cv[cv.size() - 2].fi) {
					cv[cv.size() - 2].se += cv.back().se;
					cv.pop_back();
				}
				if(left % p.se) cv.push_back(make_pair(cv.back().fi + 1, p.se - left % p.se));
				left = 0;
			}
		}
	}

	printf("1");
	return 0;
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cv.size(); i++) {
                 ~~^~~~~~~~~~~
bodyguards.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &R);
  ~~~~~^~~~~~~~~~
bodyguards.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < R; i++) scanf("%lld%lld", &rv[i].fi, &rv[i].se);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
bodyguards.cpp:25:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < C; i++) scanf("%lld%lld", &cv[i].fi, &cv[i].se);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 2304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 5928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 8412 KB Output is correct
2 Correct 113 ms 8340 KB Output is correct
3 Correct 100 ms 7704 KB Output is correct
4 Incorrect 38 ms 2808 KB Output isn't correct
5 Halted 0 ms 0 KB -