CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:kapesu8
Submission time:2016-10-14 17:25:02 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED37
#3ACCEPTED44
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s2details
#3ACCEPTED0.13 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:116:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < linked_seq.size(); i++)
                                      ^

Code

#include <iostream>
#include <string>
#include <cstdio>
#include <vector>

int main()
{
	int count;
	std::cin >> count;
	int *numbers_c = new int[count+1];
	int *numbers_cb = new int[count+1];

	bool *numbers_list = new bool[count+1];

	int *numbers = new int[count+1];
	int *numbers_i = new int[count+1];
	int *klist = new int[count*5];
	int klist_top = 0;

	std::vector<int> linked_seq;

	for(int i = 1;i <= count;i++)
	{
		std::cin >> numbers[i];
		numbers_i[numbers[i]] = i;
		numbers_c[i] = numbers[i];
		numbers_cb[i] = 0;
		numbers_list[i] = false;
	}
	for(int i = 1;i <= count;i++)
	{
		if(numbers[numbers[i]] == i && numbers[i] != i && i != 1 && numbers[i] != 1) //swap
		{
			int max = (i > numbers[i] ? i : numbers[i]);
			int min = (i > numbers[i] ? numbers[i] : i);
			int difference = max - min;

			klist[klist_top++] = max;
			klist[klist_top++] = difference;
			klist[klist_top++] = difference-1;
			klist[klist_top++] = difference;
			klist[klist_top++] = difference+1;
			klist[klist_top++] = max;

			int ival = numbers[i];
			numbers[i] = i;
			numbers[ival] = ival;


		}
	}

	int current_index = 1;
	while(1)
	{
		numbers_list[current_index] = true;
		current_index = numbers[current_index];
		if(current_index == 1)
			break;
	}
	//search first where numbers_list[i] != true && numbers[i] != i
	int last_search_index = 1;
	while(1)
	{
		int numbers_list2_i1 = 0;
		int numbers_list2_in = 0;
		for(int i = last_search_index;i <= count;i++)
		{
			if(!numbers_list[i] && !(numbers[i] == i))
			{
				numbers_list2_i1 = i;
				last_search_index = i + 1;
				break;
			}
		}
		if(numbers_list2_i1 != 0)
		{
			//search last (numbers_list2_in) in linked sequence
			numbers_list[numbers_list2_i1] = true;
			current_index = numbers[numbers_list2_i1];
			while(numbers[current_index] != numbers_list2_i1)
			{
				numbers_list[current_index] = true;
				current_index = numbers[current_index];
			}
			numbers_list2_in = current_index;
			numbers_list[numbers_list2_in] = true;

			//add linked sequence
			linked_seq.push_back(numbers_list2_in);

		}
		else
			break;
	}
	if(linked_seq.size() > 0) 
	{
		//swap first numbers_list2_in and numbers_i[1] (6 reversals)
		int numbers_list2_in = linked_seq[0];
		int max = (numbers_list2_in > numbers_i[1] ? numbers_list2_in : numbers_i[1]);
		int min = (numbers_list2_in > numbers_i[1] ? numbers_i[1] : numbers_list2_in);
		int difference = max - min;

		klist[klist_top++] = max;
		klist[klist_top++] = difference;
		klist[klist_top++] = difference-1;
		klist[klist_top++] = difference;
		klist[klist_top++] = difference+1;
		klist[klist_top++] = max;

		int inval = numbers[numbers_list2_in];
		numbers[numbers_list2_in] = 1;
		numbers[numbers_i[1]] = inval;
		//numbers_i unchanged

		for(int i = 1; i < linked_seq.size(); i++)
		{
			//swap (i+1)th numbers_list2_in and (i)th numbers_list2_in (1)
			int numbers_list2_inprev = linked_seq[i-1];
			int numbers_list2_in = linked_seq[i];

			int max = (numbers_list2_in > numbers_list2_inprev ? numbers_list2_in : numbers_list2_inprev);
			int min = (numbers_list2_in > numbers_list2_inprev ? numbers_list2_inprev : numbers_list2_in);
			int difference = max - min;

			klist[klist_top++] = max;
			klist[klist_top++] = difference;
			klist[klist_top++] = difference-1;
			klist[klist_top++] = difference;
			klist[klist_top++] = difference+1;
			klist[klist_top++] = max;

			int inval = numbers[numbers_list2_in];
			numbers[numbers_list2_in] = 1;
			numbers[numbers_list2_inprev] = inval;
		}


	}




	//solve by swapping 1. to correct position (4 reversals)
	
	current_index = 1;
	while(1)
	{
		int final_position = current_index;

		klist[klist_top++] = final_position-1;
		klist[klist_top++] = final_position-2;
		klist[klist_top++] = final_position-1;
		klist[klist_top++] = final_position;

		current_index = numbers[final_position];
		if(current_index == 1)
			break;
	}
	std::cout << klist_top << '\n';
	for(int k = 0;k < klist_top;k++)
	{
		if(klist[k] < 1)
			klist[k] = 1;
		if(klist[k] > count)
			klist[k] = count;
		std::cout << klist[k] << ' ';
	}
	



	/*for(int k = 0;k < klist_top;k++)
	{
		for(int i = 1;i <= klist[k];i++)
		{
			numbers_cb[i] = numbers_c[i];
		}
		for(int i = 1;i <= klist[k];i++)
		{
			numbers_c[i] = numbers_cb[klist[k] - i + 1];
		}
	}*/
	/*for(int i = 1;i <= count;i++)
	{
		std::cout << numbers_c[i] << ' ';
	}*/
	//std::cout << "ls:" << linked_seq.size();

	std::cin.clear();
	std::cin.get();
	std::cin.get();
	return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10
9 3 4 7 6 5 10 2 8 1

correct output
32
10 10 9 10 9 8 7 9 4 2 1 4 5 2...

user output
38
6 1 1 1 2 6 1 1 1 1 8 7 8 9 7 ...

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
650 716 982 41 133 1000 876 92...

correct output
3984
207 207 206 207 128 127 126 12...

user output
3986
521 308 307 308 309 521 902 44...

Test 3

Group: 3

Verdict: ACCEPTED

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
400046
51654 31705 31704 31705 31706 ...