Submission #71016258 - AtCoder Regular Contest 210

Contest Duration: 2025-11-16 21:00:00+0900 - 2025-11-16 23:00:00+0900 (local time) (120 minutes) Back to Home

Submission #71016258

Source Code Expand

/*
*            /$$           /$$
*           |__/          |__/
*  /$$$$$$$$ /$$ /$$$$$$$$ /$$  /$$$$$$
* |____ /$$/| $$|____ /$$/| $$ /$$__  $$
*    /$$$$/ | $$   /$$$$/ | $$| $$  \ $$
*   /$$__/  | $$  /$$__/  | $$| $$  | $$
*  /$$$$$$$$| $$ /$$$$$$$$| $$|  $$$$$$$
* |________/|__/|________/|__/ \____  $$
*                                   | $$
*                                   | $$
*                                   |__/
*/
//hj23308±£ÓÓÎÒ
//Missile±£ÓÓÎÒ
/*
* ÐÑÁËÔÚÃÎÀïÕõÔú£¬²»¾õ÷öµÁË³¯Ï¼
*/
/*
* ÎÒºÜ¸ßÐËÄãÃ»ÓÐÍüÁËÎÒ£¬µ«ÊÇÎÒÏÖÔÚ¸üÏ£ÍûÄãÒÑ¾ÍüÁËÎÒÁË¡£
* Ï£ÍûÔÚÄãµÄ¼ÇÒäÖÐ£¬ÎÒÖ»ÊÇ³¾ÍÁÒ»´é£¬´ÓÄãµÄÈ«ÊÀ½çÂ·¹ý£¬È»ºóËÄÉ¢·ÉÑï²»ÁôÏÂÒ»µãºÛ¼££¬¶øÄãÒª²»»ØÍ·µÄÍùÇ°×ß¡£
* ÎÒ¸üÏ£ÍûÎÒÖ»ÊÇ´ÓÄãµÄÈ«ÊÀ½çÂ·¹ý£¬Ö»ÊÇÂ·¹ý
*/
/*
* Ö»ÊÇÎÒÔÚÊ®×ÖÂ·¿ÚÊØÁËÌ«¾Ã£¬ÊØµ½»ÆÉ³ÈçÓêÑÚÂñÒ»ÇÐºÛ¼££¬²Å·¢ÏÖ×Ô¼ºµÈµÄÈËÒÑ¾Àë¿ªÁË¡£
*/
/*
* ÌýÎÒµÄ ±ð»ØÍ· »ØÍ·¾Í¿ÉÄÜ»áÀáÁ÷ÂúÃæ£¬»á±»»ÆÉ³ÑÚÂñ£¬ËùÒÔ¼´Ê¹Í´¿àÒ²ÒªÏòÇ°×ß
*/
/*
* ÎÒÌýµ½ÁË¡¸ÌìÐÐ½¡¡¹µÄ»ØÏì£¬ÕâÊÇÒ»¸öÎ°´ó¶·Ê¿µÄ²»Ï¢×ÔÇ¿£»
* ÎÒÌýµ½ÁË¡¸ÆÆÍò·¨¡¹µÄ»ØÏì£¬ÕâÊÇÒ»¸öºÚµÀ´òÊÖµÄÊØ»¤ÓûÍû£»
* ÎÒ¿´¼ûÁË¡¸ÉúÉú²»Ï¢¡¹µÄ¼¤µ´£¬ÕâÊÇÒ»¸öÆ×ÓµÄÎ°´óÀÖÕÂ£¡
*/
/*
* ÎÒÓÃÐé¼ÙµÄÃæ¾ßÕÕ¹Ë×ÅÏ¸ÄåµÄ¸ÐÇé£»
* ÎÒÒÔ»ªÀöµÄÒÂÎïÏÂ²Ø×Å¸¯ÀÃµÄÑªÈâ£»
* µ±ÎÒÕªÏÂÃæ¾ß£¬ÍÊÈ¥ÒÂÎï£¬¼´±ãÊÇÎÒ×îÇ×½üµÄÈË£¬Ò²ÎÞ·¨Ö±ÊÓÎÒ
*/
#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
mt19937 engine(chrono::steady_clock().now().time_since_epoch().count());
const int MOD=998244353;
const int MAXN=2e5+5;
int n;
long long a[MAXN],b[MAXN],pre[MAXN],suf[MAXN];
long long fac[MAXN],ifac[MAXN];
long long qpow(long long u,long long k)
{
	long long Ans=1;
	while(k) {
		if(k&1) Ans=Ans*u%MOD;
		k/=2;
		u=u*u%MOD;
	}
	return Ans;
}
long long inv(long long u)
{
	return qpow(u,MOD-2);
}
void Init()
{
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++) {
		fac[i]=fac[i-1]*i%MOD;
		ifac[i]=ifac[i-1]*inv(i)%MOD;
	}
}
long long C(int N,int M)
{
	return fac[N]*ifac[M]%MOD*ifac[N-M]%MOD;
}
vector<long long>N;
void DFS(int siz,int pos,int st,long long val)
{
	if(pos>siz) {
		N.emplace_back(val);
		return;
	}
	for(int i=st+1;i<=n;i++) {
		DFS(siz,pos+1,i,val+a[i]);
	}
}
vector<pair<int,pair<long long,long long>>>ans;
priority_queue<pair<long long,int>>q;
void DFS()
{
	int cnt=0;
	q.emplace(0,0);
	while(!q.empty()) {
		cnt++;
		int id=q.top().second;
		long long val=-q.top().first;
		N.emplace_back(val);
		q.pop();
		if(cnt>=3000000) break;
		if(id+1<=n) {
			if(id) q.emplace(-(val-b[id]+b[id+1]),id+1);
			q.emplace(-(val+b[id+1]),id+1);
		}
	}
	sort(N.begin(),N.end());
	for(int i=0;i<int(N.size())-1;i++) {
		if(101*N[i]<=100*N[i+1]) ans.emplace_back(i+1,mk(N[i],N[i+1]));
	}
}
void Solve()
{
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++) {
		pre[i]=pre[i-1]+b[i];
	}
	for(int i=n;i>=1;i--) {
		suf[i]=suf[i+1]+b[i];
	}
	DFS();
	long long res=1;
	for(int i=1;i<=n;i++) {
		if(suf[n-(i-1)+1]*101<=pre[i]*100) {
			ans.emplace_back(res,mk(suf[n-(i-1)+1],pre[i]));
		}
		res=(res+C(n,i))%MOD;
	}
	sort(ans.begin(),ans.end());
	ans.resize(unique(ans.begin(),ans.end())-ans.begin());
	cout<<ans.size()<<"\n";
	for(auto Node:ans) {
		cout<<Node.second.first<<" "<<Node.second.second<<" "<<Node.first<<"\n";
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		b[i]=a[i];
	}
	Init();
	Solve();
	return 0;
}

Submission Info

Submission Time	2025-11-16 22:54:39+0900
Task	E - Subset Sum Gaps
User	Ziziq
Language	C++23 (GCC 15.2.0)
Score	0
Code Size	4115 Byte
Status	WA
Exec Time	656 ms
Memory	87660 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 1000

Status

× 4

AC	× 45
WA	× 88

Set Name	Test Cases
Sample	01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 01_sample_04.txt
All	01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 01_sample_04.txt, 02_gen1_01.txt, 02_gen1_02.txt, 02_gen1_03.txt, 02_gen1_04.txt, 02_gen1_05.txt, 02_gen1_06.txt, 02_gen1_07.txt, 02_gen1_08.txt, 02_gen1_09.txt, 02_gen1_10.txt, 03_gen2_01.txt, 03_gen2_02.txt, 03_gen2_03.txt, 03_gen2_04.txt, 03_gen2_05.txt, 03_gen2_06.txt, 03_gen2_07.txt, 03_gen2_08.txt, 03_gen2_09.txt, 03_gen2_10.txt, 04_gen3_01.txt, 04_gen3_02.txt, 04_gen3_03.txt, 04_gen3_04.txt, 04_gen3_05.txt, 04_gen3_06.txt, 04_gen3_07.txt, 04_gen3_08.txt, 04_gen3_09.txt, 04_gen3_10.txt, 05_gen4_01.txt, 05_gen4_02.txt, 05_gen4_03.txt, 06_gen5_01.txt, 06_gen5_02.txt, 06_gen5_03.txt, 06_gen5_04.txt, 06_gen5_05.txt, 06_gen5_06.txt, 06_gen5_07.txt, 06_gen5_08.txt, 06_gen5_09.txt, 06_gen5_10.txt, 07_gen6_01.txt, 07_gen6_02.txt, 07_gen6_03.txt, 07_gen6_04.txt, 07_gen6_05.txt, 07_gen6_06.txt, 07_gen6_07.txt, 07_gen6_08.txt, 07_gen6_09.txt, 07_gen6_10.txt, 08_gen7_01.txt, 08_gen7_02.txt, 08_gen7_03.txt, 08_gen7_04.txt, 08_gen7_05.txt, 08_gen7_06.txt, 08_gen7_07.txt, 08_gen7_08.txt, 08_gen7_09.txt, 08_gen7_10.txt, 09_gen8_01.txt, 09_gen8_02.txt, 09_gen8_03.txt, 09_gen8_04.txt, 09_gen8_05.txt, 09_gen8_06.txt, 09_gen8_07.txt, 09_gen8_08.txt, 09_gen8_09.txt, 09_gen8_10.txt, 10_gen9_01.txt, 10_gen9_02.txt, 10_gen9_03.txt, 10_gen9_04.txt, 10_gen9_05.txt, 10_gen9_06.txt, 10_gen9_07.txt, 10_gen9_08.txt, 10_gen9_09.txt, 10_gen9_10.txt, 11_gen10_01.txt, 11_gen10_02.txt, 12_gen11_01.txt, 12_gen11_02.txt, 12_gen11_03.txt, 13_gen12_01.txt, 13_gen12_02.txt, 13_gen12_03.txt, 14_gen13_01.txt, 14_gen13_02.txt, 14_gen13_03.txt, 15_gen14_01.txt, 15_gen14_02.txt, 15_gen14_03.txt, 16_gen15_01.txt, 16_gen15_02.txt, 16_gen15_03.txt, 16_gen15_04.txt, 16_gen15_05.txt, 16_gen15_06.txt, 16_gen15_07.txt, 16_gen15_08.txt, 16_gen15_09.txt, 16_gen15_10.txt, 17_gen16_01.txt, 17_gen16_02.txt, 17_gen16_03.txt, 17_gen16_04.txt, 17_gen16_05.txt, 17_gen16_06.txt, 17_gen16_07.txt, 17_gen16_08.txt, 17_gen16_09.txt, 17_gen16_10.txt, 18_gen17_01.txt, 18_gen17_02.txt, 18_gen17_03.txt, 18_gen17_04.txt, 18_gen17_05.txt, 18_gen17_06.txt, 18_gen17_07.txt, 18_gen17_08.txt, 18_gen17_09.txt, 18_gen17_10.txt, 19_hack_double_01.txt, 19_hack_double_02.txt

Case Name	Status	Exec Time	Memory
01_sample_01.txt	AC	2 ms	3616 KiB
01_sample_02.txt	AC	1 ms	3604 KiB
01_sample_03.txt	AC	1 ms	3628 KiB
01_sample_04.txt	AC	157 ms	14224 KiB
02_gen1_01.txt	AC	70 ms	8924 KiB
02_gen1_02.txt	AC	2 ms	3676 KiB
02_gen1_03.txt	AC	1 ms	3636 KiB
02_gen1_04.txt	AC	4 ms	3888 KiB
02_gen1_05.txt	AC	2 ms	3616 KiB
02_gen1_06.txt	AC	1 ms	3772 KiB
02_gen1_07.txt	AC	17 ms	5252 KiB
02_gen1_08.txt	AC	1 ms	3628 KiB
02_gen1_09.txt	AC	17 ms	5220 KiB
02_gen1_10.txt	AC	1 ms	3672 KiB
03_gen2_01.txt	AC	614 ms	86716 KiB
03_gen2_02.txt	AC	636 ms	85492 KiB
03_gen2_03.txt	AC	630 ms	85612 KiB
03_gen2_04.txt	AC	640 ms	85660 KiB
03_gen2_05.txt	AC	639 ms	85488 KiB
03_gen2_06.txt	AC	550 ms	54564 KiB
03_gen2_07.txt	AC	596 ms	87660 KiB
03_gen2_08.txt	AC	619 ms	86316 KiB
03_gen2_09.txt	AC	648 ms	85500 KiB
03_gen2_10.txt	AC	545 ms	52748 KiB
04_gen3_01.txt	AC	650 ms	85716 KiB
04_gen3_02.txt	AC	640 ms	85824 KiB
04_gen3_03.txt	AC	646 ms	85796 KiB
04_gen3_04.txt	AC	645 ms	85740 KiB
04_gen3_05.txt	AC	634 ms	85788 KiB
04_gen3_06.txt	AC	634 ms	85768 KiB
04_gen3_07.txt	AC	650 ms	85892 KiB
04_gen3_08.txt	AC	648 ms	85820 KiB
04_gen3_09.txt	AC	650 ms	85728 KiB
04_gen3_10.txt	AC	656 ms	85812 KiB
05_gen4_01.txt	WA	550 ms	85768 KiB
05_gen4_02.txt	WA	551 ms	85888 KiB
05_gen4_03.txt	WA	551 ms	85664 KiB
06_gen5_01.txt	WA	556 ms	85884 KiB
06_gen5_02.txt	WA	578 ms	85764 KiB
06_gen5_03.txt	WA	559 ms	85892 KiB
06_gen5_04.txt	WA	586 ms	85748 KiB
06_gen5_05.txt	WA	580 ms	85728 KiB
06_gen5_06.txt	WA	582 ms	85752 KiB
06_gen5_07.txt	WA	551 ms	85768 KiB
06_gen5_08.txt	WA	586 ms	85764 KiB
06_gen5_09.txt	WA	586 ms	85732 KiB
06_gen5_10.txt	WA	586 ms	85744 KiB
07_gen6_01.txt	WA	574 ms	85528 KiB
07_gen6_02.txt	WA	562 ms	85520 KiB
07_gen6_03.txt	WA	567 ms	85524 KiB
07_gen6_04.txt	WA	546 ms	85576 KiB
07_gen6_05.txt	WA	556 ms	85544 KiB
07_gen6_06.txt	WA	576 ms	85540 KiB
07_gen6_07.txt	WA	560 ms	85532 KiB
07_gen6_08.txt	WA	553 ms	85520 KiB
07_gen6_09.txt	WA	588 ms	85596 KiB
07_gen6_10.txt	WA	549 ms	85564 KiB
08_gen7_01.txt	WA	554 ms	85740 KiB
08_gen7_02.txt	WA	573 ms	85892 KiB
08_gen7_03.txt	WA	547 ms	85740 KiB
08_gen7_04.txt	WA	555 ms	85748 KiB
08_gen7_05.txt	WA	575 ms	85744 KiB
08_gen7_06.txt	WA	536 ms	85724 KiB
08_gen7_07.txt	WA	552 ms	85788 KiB
08_gen7_08.txt	WA	583 ms	85820 KiB
08_gen7_09.txt	WA	554 ms	85764 KiB
08_gen7_10.txt	WA	533 ms	85740 KiB
09_gen8_01.txt	WA	450 ms	85724 KiB
09_gen8_02.txt	WA	555 ms	85888 KiB
09_gen8_03.txt	WA	468 ms	85724 KiB
09_gen8_04.txt	WA	453 ms	85724 KiB
09_gen8_05.txt	WA	466 ms	85740 KiB
09_gen8_06.txt	WA	474 ms	85724 KiB
09_gen8_07.txt	WA	447 ms	85884 KiB
09_gen8_08.txt	WA	558 ms	85780 KiB
09_gen8_09.txt	WA	451 ms	85768 KiB
09_gen8_10.txt	WA	452 ms	85732 KiB
10_gen9_01.txt	WA	557 ms	85820 KiB
10_gen9_02.txt	WA	585 ms	85804 KiB
10_gen9_03.txt	WA	562 ms	85716 KiB
10_gen9_04.txt	WA	549 ms	85804 KiB
10_gen9_05.txt	WA	543 ms	85812 KiB
10_gen9_06.txt	WA	546 ms	85816 KiB
10_gen9_07.txt	WA	544 ms	85724 KiB
10_gen9_08.txt	WA	553 ms	85676 KiB
10_gen9_09.txt	WA	546 ms	85820 KiB
10_gen9_10.txt	WA	552 ms	85740 KiB
11_gen10_01.txt	WA	426 ms	85712 KiB
11_gen10_02.txt	WA	425 ms	85832 KiB
12_gen11_01.txt	AC	636 ms	85764 KiB
12_gen11_02.txt	AC	643 ms	85892 KiB
12_gen11_03.txt	AC	633 ms	85816 KiB
13_gen12_01.txt	AC	617 ms	85812 KiB
13_gen12_02.txt	AC	628 ms	85768 KiB
13_gen12_03.txt	AC	635 ms	85812 KiB
14_gen13_01.txt	WA	500 ms	85540 KiB
14_gen13_02.txt	AC	502 ms	85512 KiB
14_gen13_03.txt	AC	492 ms	85604 KiB
15_gen14_01.txt	WA	478 ms	85744 KiB
15_gen14_02.txt	WA	476 ms	85808 KiB
15_gen14_03.txt	WA	476 ms	85824 KiB
16_gen15_01.txt	WA	448 ms	85816 KiB
16_gen15_02.txt	WA	449 ms	85728 KiB
16_gen15_03.txt	WA	448 ms	85820 KiB
16_gen15_04.txt	WA	446 ms	85800 KiB
16_gen15_05.txt	WA	447 ms	85892 KiB
16_gen15_06.txt	WA	444 ms	85888 KiB
16_gen15_07.txt	WA	447 ms	85740 KiB
16_gen15_08.txt	WA	447 ms	85748 KiB
16_gen15_09.txt	WA	448 ms	85800 KiB
16_gen15_10.txt	WA	447 ms	85888 KiB
17_gen16_01.txt	WA	467 ms	85804 KiB
17_gen16_02.txt	WA	469 ms	85832 KiB
17_gen16_03.txt	WA	467 ms	85744 KiB
17_gen16_04.txt	WA	465 ms	85764 KiB
17_gen16_05.txt	WA	468 ms	85760 KiB
17_gen16_06.txt	WA	469 ms	85740 KiB
17_gen16_07.txt	WA	466 ms	85744 KiB
17_gen16_08.txt	WA	467 ms	85888 KiB
17_gen16_09.txt	WA	468 ms	85816 KiB
17_gen16_10.txt	WA	463 ms	85812 KiB
18_gen17_01.txt	AC	462 ms	85816 KiB
18_gen17_02.txt	WA	462 ms	85764 KiB
18_gen17_03.txt	WA	462 ms	85744 KiB
18_gen17_04.txt	WA	467 ms	85820 KiB
18_gen17_05.txt	WA	463 ms	85820 KiB
18_gen17_06.txt	WA	467 ms	85740 KiB
18_gen17_07.txt	AC	454 ms	85760 KiB
18_gen17_08.txt	AC	460 ms	85736 KiB
18_gen17_09.txt	WA	475 ms	85744 KiB
18_gen17_10.txt	WA	463 ms	85884 KiB
19_hack_double_01.txt	WA	531 ms	85480 KiB
19_hack_double_02.txt	WA	534 ms	85544 KiB