Submission #58202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58202	2018-07-17T06:46:20 Z	정원준(#1691)	Candies (JOI18_candies)	C++11	8 / 100	108 ms	10400 KB

candies

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,ans;
L a[100010],nex[100010],pre[100010],cd[100010];

struct S{
	L val,loc,candy;
};

bool operator<(S a,S b){
	if(a.val==b.val) return a.loc<b.loc;
	return a.val>b.val;
}

bool operator==(S a,S b){
	return a.val==b.val&&a.loc==b.loc;
}

set<S>st;

int main()
{
	scanf("%lld",&n);
	L i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		nex[i]=i+1;
		pre[i]=i-1;
		cd[i]=1;
		S temp=(S){a[i],i,1};
		st.insert(temp);
	}
	nex[0]=1;
	pre[0]=0;
	nex[n+1]=n+1;
	pre[n+1]=n;
	
	/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
		{
			printf("%lld %lld\n",ii->loc,ii->val);
		}
		for(j=1;j<=n;j++)
		{
			printf("%lld ",nex[j]);
		}
		puts("");
		for(j=1;j<=n;j++)
		{
			printf("%lld ",pre[j]);
		}
		puts("");*/
	
	for(i=1;i<=(n+1)/2;i++)
	{
		set<S>::iterator now=st.begin();
		ans+=now->val;
		if(pre[now->loc]==0&&nex[now->loc]==n+1)
		{
			st.erase(now);
		}
		else if(pre[now->loc]==0)
		{	
			//puts("1");
			S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
			S inptemp=(S){nextemp.val-a[now->loc],now->loc,nextemp.candy-now->candy};
			a[now->loc]=nextemp.val-a[now->loc];
			cd[now->loc]=nextemp.candy-now->candy;
			
			pre[nex[nex[now->loc]]]=pre[now->loc];
			nex[now->loc]=nex[nex[now->loc]];
			
			st.erase(now);
			st.erase(nextemp);
			//st.insert(inptemp);
		}
		else if(nex[now->loc]==n+1)
		{
			//puts("2");
			S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
			S inptemp=(S){pretemp.val-a[now->loc],now->loc,pretemp.candy-now->candy};
			a[now->loc]=pretemp.val-a[now->loc];
			cd[now->loc]=pretemp.candy-now->candy;
			
			nex[pre[pre[now->loc]]]=nex[now->loc];
			pre[now->loc]=pre[pre[now->loc]];
			
			st.erase(now);
			st.erase(pretemp);
			//st.insert(inptemp);	
		}
		else
		{
			//puts("3");
			S nextemp=(S){a[nex[now->loc]],nex[now->loc],cd[nex[now->loc]]};
			S pretemp=(S){a[pre[now->loc]],pre[now->loc],cd[pre[now->loc]]};
			S inptemp=(S){nextemp.val+pretemp.val-a[now->loc],now->loc,nextemp.candy+pretemp.candy-now->candy};
			a[now->loc]=nextemp.val+pretemp.val-a[now->loc];
			cd[now->loc]=nextemp.candy+pretemp.candy-now->candy;
			
			/*printf("%lld %lld\n",nextemp.loc,nextemp.val);
			printf("%lld %lld\n",pretemp.loc,pretemp.val);
			printf("%lld %lld\n",inptemp.loc,inptemp.val);*/
			
			pre[nex[nex[now->loc]]]=now->loc;
			nex[now->loc]=nex[nex[now->loc]];
			
			nex[pre[pre[now->loc]]]=now->loc;
			pre[now->loc]=pre[pre[now->loc]];
			
			st.erase(now);
			st.erase(nextemp);
			st.erase(pretemp);
			st.insert(inptemp);
		}
		printf("%lld\n",ans);
		//printf("**%lld**\n",ans);
		/*for(set<S>::iterator ii=st.begin();ii!=st.end();ii++)
		{
			printf("%lld %lld\n",ii->loc,ii->val);
		}
		for(j=1;j<=n;j++)
		{
			printf("%lld ",nex[j]);
		}
		puts("");
		for(j=1;j<=n;j++)
		{
			printf("%lld ",pre[j]);
		}
		puts("");
		for(j=1;j<=n;j++)
		{
			printf("%lld ",cd[j]);
		}
		puts("");*/
	}
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:69:6: warning: variable 'inptemp' set but not used [-Wunused-but-set-variable]
    S inptemp=(S){nextemp.val-a[now->loc],now->loc,nextemp.candy-now->candy};
      ^~~~~~~
candies.cpp:84:6: warning: variable 'inptemp' set but not used [-Wunused-but-set-variable]
    S inptemp=(S){pretemp.val-a[now->loc],now->loc,pretemp.candy-now->candy};
      ^~~~~~~
candies.cpp:27:6: warning: unused variable 'j' [-Wunused-variable]
  L i,j;
      ^
candies.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
candies.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	6 ms	612 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	4 ms	852 KB	Output is correct
5	Correct	4 ms	924 KB	Output is correct
6	Correct	4 ms	924 KB	Output is correct
7	Correct	5 ms	924 KB	Output is correct
8	Correct	4 ms	1088 KB	Output is correct
9	Correct	4 ms	1088 KB	Output is correct
10	Correct	6 ms	1088 KB	Output is correct
11	Correct	4 ms	1088 KB	Output is correct
12	Correct	5 ms	1132 KB	Output is correct
13	Correct	6 ms	1132 KB	Output is correct
14	Correct	5 ms	1132 KB	Output is correct
15	Correct	4 ms	1132 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	4 ms	1132 KB	Output is correct
18	Correct	4 ms	1132 KB	Output is correct
19	Correct	4 ms	1132 KB	Output is correct
20	Correct	5 ms	1132 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	6 ms	612 KB	Output is correct
3	Correct	4 ms	852 KB	Output is correct
4	Correct	4 ms	852 KB	Output is correct
5	Correct	4 ms	924 KB	Output is correct
6	Correct	4 ms	924 KB	Output is correct
7	Correct	5 ms	924 KB	Output is correct
8	Correct	4 ms	1088 KB	Output is correct
9	Correct	4 ms	1088 KB	Output is correct
10	Correct	6 ms	1088 KB	Output is correct
11	Correct	4 ms	1088 KB	Output is correct
12	Correct	5 ms	1132 KB	Output is correct
13	Correct	6 ms	1132 KB	Output is correct
14	Correct	5 ms	1132 KB	Output is correct
15	Correct	4 ms	1132 KB	Output is correct
16	Correct	5 ms	1132 KB	Output is correct
17	Correct	4 ms	1132 KB	Output is correct
18	Correct	4 ms	1132 KB	Output is correct
19	Correct	4 ms	1132 KB	Output is correct
20	Correct	5 ms	1132 KB	Output is correct
21	Execution timed out	108 ms	10400 KB	Time limit exceeded (wall clock)
22	Halted	0 ms	0 KB	-