1621 - Jumping Around

All about problems in Volume 16. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
fsps60312
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 1621 - Jumping Around

Post by fsps60312 » Thu Aug 27, 2015 7:50 am

Hi
I think I’ve solved this problem, for safety, I made my code carefully check the validity of output before printing answer. If it’s not a valid answer, it should trigger assert().
The result should be either Accepted or Runtime Error. But it returns Wrong Answer. Why?
The code won't trigger assert() if and only if all tickets are exactly used up, ANS contains exactly 0~N-1, and according to ANS can recover all tickets properly. The first element of ANS is 0 obviously. How come it's WA if it fit all the conditions above?
Could anyone please check if my way of verifying answer is correct? Thanks!

My code:

Code: Select all

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<int>ANS;
void solve(int a,int b,int c)
{
	int A=a,B=b,C=c;
	int loc;
	ANS.clear();
	if(C==3)
	{
		static int bse[6]={0,3,1,4,2,5};
		for(int i=0;i<6;i++)ANS.push_back(bse[i]);
		B-=2,C-=3;
		loc=5;
	}
	else if(C%3==1)
	{
		int cnt=(C-1)/3;
		ANS.push_back(0);
		loc=0;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc+=3);
		ANS.push_back(loc-=2);B--;
		for(int i=1;i<=cnt;i++,C--)ANS.push_back(loc-=3);
		ANS.push_back(loc+=1);A--;
		for(int i=1;i<=cnt;i++,C--)ANS.push_back(loc+=3);
		ANS.push_back(loc+=2);B--;
	}
	else if(C%3==2)
	{
		int cnt=(C-2)/3;
		ANS.push_back(0);
		loc=0;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc+=3);
		ANS.push_back(loc-=1);A--;
		for(int i=1;i<=cnt;i++,C--)ANS.push_back(loc-=3);
		ANS.push_back(loc-=1);A--;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc+=3);
	}
	else
	{
		int cnt=(C-3)/3;
		ANS.push_back(0);
		loc=0;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc+=3);
		ANS.push_back(loc+=1);A--;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc-=3);
		ANS.push_back(loc+=1);A--;
		for(int i=0;i<=cnt;i++,C--)ANS.push_back(loc+=3);
	}
	assert(C==0);
	for(;A>1;A--)ANS.push_back(loc+=1);
	if(B%2==0)
	{
		int cnt=B/2;
		for(int i=0;i<cnt;i++,B--)ANS.push_back(loc+=2);
		ANS.push_back(loc+=1);A--;
		for(int i=0;i<cnt;i++,B--)ANS.push_back(loc-=2);
	}
	else
	{
		int cnt=B/2;
		for(int i=0;i<=cnt;i++,B--)ANS.push_back(loc+=2);
		ANS.push_back(loc-=1);A--;
		for(int i=0;i<cnt;i++,B--)ANS.push_back(loc-=2);
	}
	assert(A==0&&B==0&&C==0&&ANS.size()==N);
	printf("%d",ANS[0]);
	for(int i=1,v;i<ANS.size();i++)
	{
		printf(" %d",ANS[i]);
		v=ANS[i]-ANS[i-1];
		switch(v)
		{
			case -1:
			case 1:A++;break;
			case -2:
			case 2:B++;break;
			case -3:
			case 3:C++;break;
			default:assert(0);
		}
	}
	assert(A==a&&B==b&&C==c);
	puts("");
	sort(ANS.begin(),ANS.end());
	for(int i=0;i<ANS.size();i++)assert(ANS[i]==i);
}
int main()
{
	int T,A,B,C;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&A,&B,&C);
		assert(A>=3&&B>=3&&C>=3);
		N=A+B+C+1;
		solve(A,B,C);
	}
	return 0;
}
//01234567890
//012123
//03312424
//03314225
//044135226
//05514623737
//05516427338
//066157248339

fsps60312
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 1621 - Jumping Around

Post by fsps60312 » Thu Aug 27, 2015 9:18 am

Solved :)
Should I remove previous post or code?

Post Reply

Return to “Volume 16 (1600-1699)”