QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618639#8790. First Billionucup-team134#TL 980ms4140kbC++171.7kb2024-10-07 01:28:262024-10-07 01:28:26

Judging History

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

  • [2024-10-07 01:28:26]
  • 评测
  • 测评结果:TL
  • 用时:980ms
  • 内存:4140kb
  • [2024-10-07 01:28:26]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;

mt19937 rng(time(NULL));
int main()
{
	int n;
	scanf("%i",&n);
	vector<bool> in(n);
	int sm=0;
	vector<int> c(n);
	for(int i=0;i<n;i++){
		scanf("%i",&c[i]);
	}
	while(1){
		fill(all(in),0);
		sm=0;
		for(int i=0;i<n/2;i++){
			int x=rng()%n;
			while(in[x])x=rng()%n;
			in[x]=1;
			sm+=c[x];
		}
		int treba=1e9;
		vector<pair<int,int>> aa,bb;
		while(1){
			aa.clear(),bb.clear();
			for(int i=0;i<n;i++){
				if(in[i])aa.pb({c[i],i});
				else bb.pb({c[i],i});
			}
			sort(all(aa));
			sort(all(bb));
			int j=sz(bb)-1;
			pair<int,int> sta={-1,-1};
			int bst=abs(sm-treba);
			for(int i=0;i<sz(aa);i++){
				int ns=sm-aa[i].f+bb[j].f;
				int xx=abs(ns-treba);
				if(xx<bst){
					bst=xx;
					sta={aa[i].s,bb[j].s};
				}
				while(j>0){
					int nns=sm-aa[i].f+bb[j-1].f;
					int xxx=abs(nns-treba);
					if(xxx>xx)break;
					ns=nns;
					xx=xxx;
					j--;
					if(xx<bst){
						bst=xx;
						sta={aa[i].s,bb[j].s};
					}
				}
			}
			//printf("Swap %i %i!  %i\n",sta.f,sta.s,sm);
			if(sta.f==-1)break;
			in[sta.f]=0;
			in[sta.s]=1;
			sm-=c[sta.f];
			sm+=c[sta.s];
			//printf("sled: %i\n",sm);
			if(bst==0){
				printf("%i",n/2);
				for(int i=0;i<n;i++){
					if(in[i]){
						printf(" %i",i+1);
					}
				}
				printf("\n");
				return 0;
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10
386413329 88494216 245947398 316438989 192751270 204627269 65749456 3938400 150458676 345180997

output:

5 1 5 6 7 9

result:

ok OK (n = 10)

Test #2:

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

input:

10
119486233 299942886 169540407 349937991 597883752 32230162 140514533 57341098 12602102 220520836

output:

5 1 3 4 7 10

result:

ok OK (n = 10)

Test #3:

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

input:

14
384615281 84612238 83310504 54746763 142296081 56775470 128760350 343006424 177232390 214368720 67220468 21895072 16352717 224807522

output:

7 1 6 7 9 10 12 13

result:

ok OK (n = 14)

Test #4:

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

input:

14
270208635 14270307 89661499 113578022 47687195 101043954 38775146 208193324 650676076 351701957 3427619 59535626 24230888 27009752

output:

7 5 7 8 9 11 13 14

result:

ok OK (n = 14)

Test #5:

score: 0
Accepted
time: 8ms
memory: 3868kb

input:

20
61638928 106712373 5946815 178135484 4937573 111395400 15504655 67139983 101814514 312223647 130341028 43244171 37671364 54108486 337181317 37924824 153793862 70383750 102917244 66984582

output:

10 1 2 3 6 7 15 16 17 19 20

result:

ok OK (n = 20)

Test #6:

score: 0
Accepted
time: 2ms
memory: 3864kb

input:

20
67858098 61231428 99398662 1883806 82465954 303619377 87516412 154956240 94872199 76508350 13276828 136541811 203282099 99160366 127539385 13364660 141176136 39751629 67888657 127707903

output:

10 1 3 4 5 8 11 12 13 14 17

result:

ok OK (n = 20)

Test #7:

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

input:

24
17125795 281143405 10375259 196293002 158174864 34520650 52919232 87393970 99085271 62281508 67168428 55174991 54533464 51393059 89276370 41441658 72793517 30466999 73758332 97064918 111541434 142047546 12934221 101092107

output:

12 1 2 6 7 8 9 11 12 14 16 21 24

result:

ok OK (n = 24)

Test #8:

score: 0
Accepted
time: 7ms
memory: 3868kb

input:

24
70224368 148769600 36654748 23404220 15009825 57449487 46896672 6065662 10377031 133719710 23220853 184445684 8462667 88501546 155244839 229323557 140109402 52520271 78995771 75721556 87987586 118427778 107013825 101453342

output:

12 1 3 5 7 10 11 12 17 19 20 21 23

result:

ok OK (n = 24)

Test #9:

score: 0
Accepted
time: 166ms
memory: 3840kb

input:

28
122321206 60841271 22767116 183943582 6247754 32767541 19129802 21313874 144503909 59360441 12259051 19044256 50267333 25766572 133411289 32253746 102412217 46186594 55413161 39907615 52325783 86862071 185310732 138228874 22000146 149813853 98156445 77183766

output:

14 3 7 9 10 13 14 19 20 21 22 23 24 25 27

result:

ok OK (n = 28)

Test #10:

score: 0
Accepted
time: 167ms
memory: 3924kb

input:

28
213829745 40823140 14876795 22548901 35958464 159026037 106482651 52655603 76733934 102794554 100713772 80174862 125840182 3619651 74158077 27699586 14743901 68385227 55117143 39623241 67325444 95072408 46052588 46086093 11650160 66077724 149558313 102371804

output:

14 3 5 6 10 11 13 16 17 19 20 21 22 25 27

result:

ok OK (n = 28)

Test #11:

score: 0
Accepted
time: 980ms
memory: 3844kb

input:

30
38319400 42378812 172927254 71697590 118171420 5615707 8117586 107362865 18142211 89646810 51847201 37450061 138487251 116358215 15432103 13621837 15084921 15012145 42848714 71166566 37074067 11354748 10702902 244865332 41244161 102695984 217681174 21564320 89607508 33521135

output:

15 2 3 5 6 11 12 14 16 18 20 21 23 24 25 28

result:

ok OK (n = 30)

Test #12:

score: -100
Time Limit Exceeded

input:

30
239221492 41835739 80260950 47743386 50052259 31410042 1676838 63813733 47622772 150506632 188312503 190432229 6783832 111319580 122183547 37258127 12116231 29322396 58095114 47089744 9262724 204673438 11840273 64585542 11797425 4134848 56164171 30717831 46921664 2844938

output:


result: