QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618832#7750. Revenge on My BosslixpWA 389ms6784kbC++141.4kb2024-10-07 10:47:292024-10-07 10:47:31

Judging History

你现在查看的是最新测评结果

  • [2024-10-07 10:47:31]
  • 评测
  • 测评结果:WA
  • 用时:389ms
  • 内存:6784kb
  • [2024-10-07 10:47:29]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

const int N = 1e5+10;
long long sumb, summi[N];
int n;

struct Node{
	int a, b, c, id;
	int minus, con;
}a[N];

bool cmp(Node a, Node b){
	if(a.minus <= 0 && b.minus <= 0)
		return a.con > b.con;
	if(a.minus <= 0 || b.minus <= 0)
		return a.minus < b.minus;
	return a.con + a.minus < b.con + b.minus; 
}

bool judge(long long x){
	for(int i = 1 ; i <= n ; i++){
		a[i].con = sumb - a[i].a + x / a[i].c;
	}
	sort(a+1, a+n+1, cmp);
	
	long long summi = 0, maxx = 0;
	for(int i = 1 ; i <= n ; i++){
		summi + a[i].minus;
		long long temp = 1ll * a[i].c * (sumb + summi + a[i].b);
		if(temp > maxx)
			maxx = temp;
	} 
	return maxx <= x;
}

void solve(){
	memset(a, 0, sizeof(a));
	sumb = 0;
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i].a >> a[i].b >> a[i].c;
		a[i].id = i;
		
		sumb += a[i].b ;
		a[i].minus = a[i].a - a[i].b;
	}
	
	
	long long l = 0, r = 1e18;
    while (l + 1 < r) {
        long long mid = l + (r - l) / 2;
        if (judge(mid))
            r = mid;
        else
            l = mid;
    }
	judge(r);
	for(int i = 1 ; i <= n ; i++){
		cout << a[i].id << " ";
	}
	cout << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin >> T;
	while(T--){
		solve();
	}
	return 0;
} 

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5992kb

input:

2
4
1 1 4
5 1 5
1 9 1
9 8 1
9
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 8
3 2 7

output:

3 1 2 4 
3 8 4 2 5 9 7 1 6 

result:

ok correct

Test #2:

score: 0
Accepted
time: 313ms
memory: 6112kb

input:

1
100000
581297 102863 1
742857 42686 1
676710 233271 1
443055 491162 1
442056 28240 1
769277 331752 1
8608 369730 1
495112 525554 1
787449 938154 1
441186 850694 1
84267 925450 1
740811 32385 1
834021 37680 1
257878 564126 1
90618 914340 1
239641 463103 1
40687 343062 1
587737 458554 1
103684 48666...

output:

70717 6151 48237 28851 35679 19561 94252 73342 13089 34865 69194 82763 50242 22597 3745 24913 97923 53671 77581 47428 82224 93567 61401 50007 4886 54152 28731 91278 99937 6691 26840 6048 46204 66044 60735 44469 20513 45842 18701 46818 27203 9261 50507 8020 72391 54368 86201 18839 64763 61758 40939 3...

result:

ok correct

Test #3:

score: 0
Accepted
time: 307ms
memory: 6212kb

input:

1
99999
30245 831673 1
495617 185056 1
53028 422589 1
503558 778900 1
636981 480008 1
966864 78785 1
644954 303138 1
153080 225499 1
876411 832264 1
758904 549009 1
945000 441995 1
83780 789901 1
883282 832556 1
300776 548075 1
806599 108342 1
354979 831549 1
152110 819163 1
613891 812479 1
856259 6...

output:

42779 26176 16432 93736 36110 21022 69840 33300 88899 48735 97468 24934 58044 16598 54398 41611 25297 90410 54385 14754 38513 7374 40518 45724 3741 95478 36354 5270 92123 87433 5901 57489 42968 40570 60847 61715 65894 68944 27887 3727 38578 14748 15072 79314 41234 42830 79639 35429 60443 63782 12370...

result:

ok correct

Test #4:

score: -100
Wrong Answer
time: 389ms
memory: 6784kb

input:

1
100000
361850 684411 2
188930 167748 2
676274 449963 1
970095 784305 1
412379 854673 1
208323 612179 1
296548 633970 1
560983 633064 2
848966 248363 2
741057 340814 1
393854 435721 2
302707 834494 1
229770 235051 2
875992 747523 2
314215 448795 1
531181 809914 2
786505 95721 1
86557 773136 1
44527...

output:

95323 17982 6682 41441 84223 14964 28720 57534 70472 94854 66622 93668 48920 22168 52514 91864 53874 4818 8212 4065 34961 84790 33368 23450 82636 29214 24270 30964 60787 95096 12729 61369 76678 13298 1878 58777 96849 31192 39517 63293 2095 27412 26464 89439 97470 56123 298 34689 13391 495 55885 2207...

result:

wrong answer Wrong Answer on Case#1