QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#189740#3872. Gym BadgesTalaodi0 76ms10288kbC++144.8kb2023-09-27 20:34:242023-09-27 20:34:24

Judging History

This is the latest submission verdict.

  • [2023-09-27 20:34:24]
  • Judged
  • Verdict: 0
  • Time: 76ms
  • Memory: 10288kb
  • [2023-09-27 20:34:24]
  • Submitted

answer

#include <bits/stdc++.h>

namespace IO {
	template <class Stream>
	Stream& fmtbase(Stream& out, const char* format) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				throw std::invalid_argument("Error Number of Parameters!");
			}
			
			out << *format;
		}
		
		return out;
	}
	
	template <class Stream, class Fst, class... Nxt>
	Stream& fmtbase(Stream& out, const char* format, const Fst& value, const Nxt&... nxt) {
		for (; *format; format++) {
			if (*format == '{' && *(format + 1) == '}') {
				out << value;
				return fmtbase(out, format + 2, nxt...);
			} 
			
			out << *format;
		}
		
		throw std::invalid_argument("Error Number of Parameters!");
	}
	
	template <class... Ps>
	std::string to_string(const char* format, const Ps&... ps) {
		std::stringstream ss;
		fmtbase(ss, format, ps...);
		return ss.str();
	}

	template <class... Ps>
	std::ostream& fmtout(const char* format, const Ps&... ps) {
		return fmtbase(std::cout, format, ps...);
	}
	
	template <class... Ps>
	std::ostream& fmterr(const char* format, const Ps&... ps) {
		return fmtbase(std::cerr, format, ps...);
	}
	
	std::istream& allin() {
		return std::cin;
	}
	
	template <class Fst, class ... Nxt>
	std::istream& allin(Fst& fst, Nxt&... nxt) {
		std::cin >> fst;
		return allin(nxt...);
	}
	
	template <class Iter>
	std::istream& rangin(Iter begin, Iter end) {
		while (begin != end) {
			std::cin >> *begin;
			begin++;
		}
		
		return std::cin;
	}
	
	namespace Fast {
		bool sync = false;
		
		char buf[1 << 23];
		char *p1 = buf, *p2 = buf;
		
		void sync_with_ios(bool s) {
			sync = s;
		}
		
		char getchar() {
			if (sync) {
				return (char) std::cin.get();
			}
			else {
				if (p1 == p2) {
					p1 = buf;
					p2 = p1 + fread(buf, 1, 1 << 22, stdin);
				}
				
				if (p1 == p2) {
					return EOF;
				}
				else {
					char res = *p1;
					p1++;
					return res;
				}
			}
		}
		
		void read() { }
		
		template <class T, class... U>
		void read(T& x, U&... us) {
			x = 0;
			T pos = 1;
			
			char c = getchar();
			while (!isdigit(c)) {
				if (c == '-') {
					pos = -1;
				}
				
				c = getchar();
			}
			
			while (isdigit(c)) {
				x = 10 * x + c - '0';
				c = getchar();
			}
			
			x *= pos;
			read(us...);
		}
		
		template <class T>
		void write(const T& t) {
			if (t > 10) {
				write(t / 10);
			}
			
			std::cout << (int) (t % 10);
		}
	}
}

namespace Solve {
	using namespace IO;

	using ll = long long;
	using ul = unsigned long long;
	using db = double;
	using ld = long double;
	using ui = unsigned int;
	using ib = __int128;
	using ub = __uint128_t;

	int const INF = std::numeric_limits<int>::max();
	int const NINF = std::numeric_limits<int>::min();
	ll const LINF = std::numeric_limits<ll>::max();
	ll const LNINF = std::numeric_limits<ll>::min();
	ld const EPS = 1e-6;

	std::mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());

	ll rnd(ll l, ll r) {
		return std::uniform_int_distribution<ll>(l, r)(mt);
	}

	template <class T>
	inline int isz(const T& v) {
		return v.size();
	}

	template <class T>
	inline T& ckmx(T& a, T b) {
		return a < b ? (a = b) : a;
	}

	template <class T>
	inline T& ckmi(T& a, T b) {
		return a > b ? (a = b) : a;
	}

    int const N = 5e5 + 10;

    struct Val {
        int c, x;
    };

    Val a[N + 1];
    int n;

	void main() {
        std::cin >> n;
        for (int i = 1; i <= n; i++) {
            std::cin >> a[i].x;
        }

        for (int i = 1; i <= n; i++) {
            std::cin >> a[i].c;
        }

        std::sort(a + 1, a + n + 1, [&](const Val& a, const Val& b) {
            return std::max(a.c, a.x) < std::max(b.c, b.x);
        });

        std::priority_queue<int> que;
        int ans = 0;
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (sum <= a[i].c) {
                sum += a[i].x;
                ans++;
                que.push(a[i].x);
            }
            else if (que.top() > a[i].x) {
                sum -= que.top();
                que.pop();
                que.push(a[i].x);
                sum += a[i].x;
            }
        }

        fmtout("{}\n", ans);
	}

	void init() {

	}

	void clear() {

	}
}

signed main() {
#ifndef ONLINE_JUDGE
	auto input_file = freopen("disorder.in", "r", stdin);
	auto output_file = freopen("disorder.out", "w", stdout);
#endif
	
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	
	int t = 1;
	// std::cin >> t;

	Solve::init();
	
	for (int id = 1; id <= t; id++) {
		Solve::main();
		Solve::clear();
	}

#ifndef ONLINE_JUDGE
	std::cout.flush();
	fclose(input_file);
	fclose(output_file);
#endif

	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 15
Accepted
time: 1ms
memory: 5540kb

input:

8
539270098 632706230 269629236 114860227 516388668 106926736 442326081 489479590
349109371 304195858 1 1 1 1 1 272176035

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5588kb

input:

8
709047428 992101994 911394172 790816372 955920979 601260981 382158825 576258298
1 1 1 1 1 1 1 1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5540kb

input:

10
410225545 331027005 171655992 23993846 574501736 812513369 560289640 118944002 140595187 271274589
101761486 138941857 1 1 386041033 124577204 10463923 1 171169400 349156480

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5540kb

input:

10
536897107 501305556 788210776 663372540 52135338 652045195 406681332 17197090 503608396 436757332
42258645 188386343 54514746 103557391 1 53439943 1 1 235340362 407283951

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 5560kb

input:

10
329812627 580947084 875802829 648324811 287296765 747107865 765657366 563755052 498953661 684776526
1 1 113144166 1 503793060 183144317 99738328 1 1 271526219

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 5584kb

input:

10
322161776 554303213 421740595 270520769 292452403 434399611 384639892 116730549 114181770 607745841
1 198389486 1 223831462 1 65167091 1 862668690 498505120 268278795

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5548kb

input:

9
299075145 581580990 10268 298645450 316639453 445559321 438713303 155454790 238247173
6103 161145018 523141 9933 3079 9760 280695703 3842 585375893

output:

3

result:

ok single line: '3'

Test #8:

score: -15
Wrong Answer
time: 1ms
memory: 5556kb

input:

10
199149756 11986933 23690204 318151367 403432267 718745502 285161430 372719141 276300797 360593562
23503789 568223837 32202385 117719364 328393737 30037066 111973850 167956939 180364075 62469560

output:

3

result:

wrong answer 1st lines differ - expected: '4', found: '3'

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 9
Accepted
time: 52ms
memory: 7504kb

input:

499024
24194059 58419582 93795671 46748573 538530 94101772 6557176 45861806 13697565 74131600 86230763 495874 93328371 85034659 58261516 3311420 83620814 92145308 62793177 67970802 63891191 62175600 59686038 44916927 32817940 23191454 40796822 55385422 97662235 82408332 33350127 65553532 70025555 47...

output:

1792

result:

ok single line: '1792'

Test #22:

score: 0
Accepted
time: 60ms
memory: 7924kb

input:

499046
94426972 18856284 64542583 61930781 29300775 96585573 76511591 62642337 70487218 72575097 68384 8226673 26676879 34380253 26677387 74692670 35914788 2175294 61456543 3976881 50687285 29547500 67867939 63687754 60356596 29604912 13846674 15347276 92319238 4137253 65823661 37636416 74833506 483...

output:

2589

result:

ok single line: '2589'

Test #23:

score: 0
Accepted
time: 54ms
memory: 7600kb

input:

499945
75086610 20430906 19432043 71361042 36665247 91270707 57153810 63125108 4170891 11274485 51914724 86096991 81622910 89756946 81666672 34687783 53295391 10237329 44484436 71565032 12593955 51284876 18960654 97115345 71028167 43172268 61003609 90748191 52980960 84026952 33719653 39455068 737089...

output:

2399

result:

ok single line: '2399'

Test #24:

score: 0
Accepted
time: 61ms
memory: 8488kb

input:

499181
81960960 93399006 57762044 68542540 40284787 41893029 82550813 81956582 80073846 38532595 38691803 40257359 71220582 15724567 81263354 11231790 91029524 89902053 86356229 19876341 79914712 59756687 46196282 33547977 8509584 62652621 18818233 86368449 15974151 37231717 70147170 4568700 1806191...

output:

2922

result:

ok single line: '2922'

Test #25:

score: 0
Accepted
time: 56ms
memory: 8228kb

input:

499975
54792433 53437075 50471711 61354519 62664352 88007726 71581615 42728389 46375545 31189677 72407210 51251012 54346926 84638513 95383571 26395242 41436731 78550437 88677233 88188763 32780907 37878541 48471392 43353618 37239437 74627658 68219343 88710946 98200793 79326876 84136158 98085079 89458...

output:

2638

result:

ok single line: '2638'

Test #26:

score: 0
Accepted
time: 62ms
memory: 8488kb

input:

499964
920146 295707 161191 1474 622334 782633 188798 678190 227363 68753 308280 790267 667361 755895 99095 304744 61896 227361 199289 888651 587856 12807 29960 344592 22601 609241 335654 397456 153427 298175 958697 787233 187799 145534 461063 896741 544381 418496 515252 791633 452029 892569 630103 ...

output:

21783

result:

ok single line: '21783'

Test #27:

score: 0
Accepted
time: 49ms
memory: 9404kb

input:

499953
684270 628507 799704 989598 684807 487942 778559 496672 813311 868169 784310 679989 537938 662819 333336 162463 284521 711361 436461 67465 39448 184679 96998 675976 297977 253234 396055 78633 690384 442011 253178 327129 643970 706345 979561 648490 829546 933761 317738 148528 495206 79348 5010...

output:

4525

result:

ok single line: '4525'

Test #28:

score: 0
Accepted
time: 58ms
memory: 9168kb

input:

499538
789959 386479 285010 800685 608461 548431 486060 517493 337155 863988 260006 161721 709092 844086 419659 141500 560059 290751 591435 186666 254722 435566 122531 538132 870784 399897 221045 107206 428062 828333 701144 174456 763540 604432 792770 842812 950853 506426 964855 714626 910704 676395...

output:

15882

result:

ok single line: '15882'

Test #29:

score: 0
Accepted
time: 62ms
memory: 9460kb

input:

499487
851435 422481 763100 221834 59699 97318 587331 535646 943483 490260 403784 339554 44189 648117 296828 656679 949633 334070 977567 816723 115378 317216 95560 623954 659141 414075 727905 409254 203289 853487 969543 435526 573039 94306 183793 489409 591838 414302 983422 655303 343739 444600 9562...

output:

21013

result:

ok single line: '21013'

Test #30:

score: 0
Accepted
time: 64ms
memory: 8148kb

input:

499667
779763 263882 889301 78862 191874 75041 559293 752584 699886 525310 193650 4782 177615 573872 130796 968366 879324 622344 459661 913140 659102 438897 419290 615726 338068 436782 479778 59880 702330 262202 153038 649570 791151 520928 736451 684152 712746 751712 784287 881048 916000 506681 5966...

output:

31312

result:

ok single line: '31312'

Test #31:

score: 0
Accepted
time: 76ms
memory: 8404kb

input:

499311
3530 4899 7266 3489 770 344 2390 4144 7703 7832 7524 1670 5797 8529 138 229 7486 9112 2101 579 8934 3824 3161 8715 34 1615 8747 8185 8584 4455 3036 9419 3510 5043 2267 9603 4995 1941 1662 2994 918 8155 8632 876 6806 3964 4043 2255 1678 5083 5091 6964 2777 67 7307 9968 463 9118 4834 498 5554 1...

output:

226514

result:

ok single line: '226514'

Test #32:

score: -9
Wrong Answer
time: 72ms
memory: 10288kb

input:

499217
9270 7679 8890 7484 5663 1588 1399 9433 9324 1232 9525 7513 3417 4116 8539 8591 1965 5588 2378 2707 1370 1230 1814 6548 1779 1142 7932 9486 5044 1997 5992 9999 7774 2165 1811 5699 3151 7724 726 918 4366 9908 9838 2231 2833 8259 2654 1538 9098 7072 4055 9696 3672 8136 4534 4430 694 5305 9041 2...

output:

266395

result:

wrong answer 1st lines differ - expected: '266396', found: '266395'

Subtask #3:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 2ms
memory: 5628kb

input:

4920
343676952 471362068 183764630 14272498 286605010 453007536 667797750 174763306 161753738 692259390 402384334 207809675 24816038 135559720 2349171 268297289 158915976 311483232 237276350 130673100 523233652 177852180 84082840 350906472 27172979 107661274 8628817 205814954 636498502 115751626 451...

output:

199

result:

wrong answer 1st lines differ - expected: '200', found: '199'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%