Submission #74718549

Source Code Expand

// https://atcoder.jp/contests/arc217/submissions/74715330
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e7+5;
int n,m,a[N],prt[N],T;
int gf(int x){
	while(x != prt[x]){
		x = prt[x] = prt[prt[x]];
	}
	return x;
}
void merge(int x,int y,int v){x=gf(x),y=gf(y);if(x!=y)prt[x]=y;}
void solve()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=0;i<=m;i++)prt[i]=i;
	int nl=0,nr=m,all=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>nr-nl)continue;
		if(a[i]<=(nr-nl+1)/2)
		{
			all+=a[i];
			for(int j=nl;j<=nl+a[i]-1;j++)merge(j,j+a[i],-a[i]);
			nl+=a[i];
		}
		else
		{
			for(int j=nl+a[i];j<=nr;j++)merge(j,j-a[i],a[i]);
			nr=nl+a[i]-1;
		}
	}
	ll ans=0;
	for(int i=0;i<=m;i++)ans^=1ll*i*(all+(i-gf(i)));
	printf("%lld\n",ans);
}
int main()
{
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

Submission Info

Submission Time
Task D - Greedy Customer
User bananabot
Language C++23 (GCC 15.2.0)
Score 0
Code Size 892 Byte
Status TLE
Exec Time > 2000 ms
Memory 201076 KiB

Compile Error

./Main.cpp: In function 'void merge(int, int, int)':
./Main.cpp:13:28: warning: unused parameter 'v' [-Wunused-parameter]
   13 | void merge(int x,int y,int v){x=gf(x),y=gf(y);if(x!=y)prt[x]=y;}
      |                        ~~~~^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
AC × 61
TLE × 20
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 01_handmade_10.txt, 01_handmade_11.txt, 01_handmade_12.txt, 01_handmade_13.txt, 01_handmade_14.txt, 01_handmade_15.txt, 01_handmade_16.txt, 01_handmade_17.txt, 01_handmade_18.txt, 01_handmade_19.txt, 01_handmade_20.txt, 01_handmade_21.txt, 01_handmade_22.txt, 01_handmade_23.txt, 01_handmade_24.txt, 01_handmade_25.txt, 01_handmade_26.txt, 01_handmade_27.txt, 01_handmade_28.txt, 01_handmade_29.txt, 01_handmade_30.txt, 01_handmade_31.txt, 01_handmade_32.txt, 01_handmade_33.txt, 01_handmade_34.txt, 01_handmade_35.txt, 01_handmade_36.txt, 01_handmade_37.txt, 01_handmade_38.txt, 01_handmade_39.txt, 01_handmade_40.txt, 01_handmade_41.txt, 01_handmade_42.txt, 01_handmade_43.txt, 01_handmade_44.txt, 01_handmade_45.txt, 01_handmade_46.txt, 01_handmade_47.txt, 01_handmade_48.txt, 01_handmade_49.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3624 KiB
01_handmade_00.txt AC 132 ms 200944 KiB
01_handmade_01.txt AC 135 ms 201076 KiB
01_handmade_02.txt TLE > 2000 ms 198636 KiB
01_handmade_03.txt TLE > 2000 ms 198708 KiB
01_handmade_04.txt AC 109 ms 199152 KiB
01_handmade_05.txt AC 258 ms 200980 KiB
01_handmade_06.txt AC 264 ms 201072 KiB
01_handmade_07.txt AC 133 ms 201076 KiB
01_handmade_08.txt AC 135 ms 200952 KiB
01_handmade_09.txt AC 142 ms 200944 KiB
01_handmade_10.txt AC 135 ms 200952 KiB
01_handmade_11.txt AC 297 ms 200968 KiB
01_handmade_12.txt TLE > 2000 ms 198700 KiB
01_handmade_13.txt TLE > 2000 ms 198704 KiB
01_handmade_14.txt TLE > 2000 ms 200628 KiB
01_handmade_15.txt AC 645 ms 200944 KiB
01_handmade_16.txt AC 337 ms 201004 KiB
01_handmade_17.txt AC 263 ms 201072 KiB
01_handmade_18.txt AC 183 ms 136704 KiB
01_handmade_19.txt AC 266 ms 200952 KiB
01_handmade_20.txt AC 280 ms 200832 KiB
01_handmade_21.txt AC 309 ms 200980 KiB
01_handmade_22.txt AC 229 ms 200980 KiB
01_handmade_23.txt AC 225 ms 201076 KiB
01_handmade_24.txt AC 622 ms 200936 KiB
01_handmade_25.txt AC 598 ms 200876 KiB
01_handmade_26.txt AC 596 ms 200952 KiB
01_handmade_27.txt TLE > 2000 ms 200620 KiB
01_handmade_28.txt AC 154 ms 201076 KiB
01_handmade_29.txt AC 947 ms 201004 KiB
01_handmade_30.txt TLE > 2000 ms 200620 KiB
01_handmade_31.txt TLE > 2000 ms 200652 KiB
01_handmade_32.txt TLE > 2000 ms 200652 KiB
01_handmade_33.txt TLE > 2000 ms 200584 KiB
01_handmade_34.txt TLE > 2000 ms 200492 KiB
01_handmade_35.txt TLE > 2000 ms 200556 KiB
01_handmade_36.txt TLE > 2000 ms 200492 KiB
01_handmade_37.txt TLE > 2000 ms 200628 KiB
01_handmade_38.txt TLE > 2000 ms 200556 KiB
01_handmade_39.txt TLE > 2000 ms 200520 KiB
01_handmade_40.txt TLE > 2000 ms 200624 KiB
01_handmade_41.txt AC 1565 ms 200952 KiB
01_handmade_42.txt AC 1306 ms 200828 KiB
01_handmade_43.txt TLE > 2000 ms 200624 KiB
01_handmade_44.txt TLE > 2000 ms 200624 KiB
01_handmade_45.txt TLE > 2000 ms 200584 KiB
01_handmade_46.txt AC 649 ms 200948 KiB
01_handmade_47.txt AC 629 ms 201072 KiB
01_handmade_48.txt AC 596 ms 200980 KiB
01_handmade_49.txt AC 520 ms 200952 KiB
02_random_00.txt AC 182 ms 23396 KiB
02_random_01.txt AC 187 ms 23444 KiB
02_random_02.txt AC 185 ms 23416 KiB
02_random_03.txt AC 181 ms 23356 KiB
02_random_04.txt AC 233 ms 199800 KiB
02_random_05.txt AC 236 ms 199540 KiB
02_random_06.txt AC 247 ms 199672 KiB
02_random_07.txt AC 241 ms 199540 KiB
02_random_08.txt AC 246 ms 200948 KiB
02_random_09.txt AC 246 ms 199600 KiB
02_random_10.txt AC 250 ms 199800 KiB
02_random_11.txt AC 241 ms 200108 KiB
02_random_12.txt AC 258 ms 200624 KiB
02_random_13.txt AC 232 ms 199160 KiB
02_random_14.txt AC 138 ms 200428 KiB
02_random_15.txt AC 210 ms 199800 KiB
02_random_16.txt AC 402 ms 200176 KiB
02_random_17.txt AC 375 ms 200488 KiB
02_random_18.txt AC 39 ms 29056 KiB
02_random_19.txt AC 83 ms 61224 KiB
02_random_20.txt AC 254 ms 200876 KiB
02_random_21.txt AC 262 ms 200952 KiB
02_random_22.txt AC 258 ms 201072 KiB
02_random_23.txt AC 263 ms 201000 KiB
02_random_24.txt AC 563 ms 200980 KiB
02_random_25.txt AC 359 ms 199444 KiB
02_random_26.txt AC 334 ms 199208 KiB
02_random_27.txt AC 571 ms 200940 KiB
02_random_28.txt AC 565 ms 201072 KiB
02_random_29.txt AC 564 ms 200832 KiB