CSES - Datatähti 2017 alku - Results
Submission details
Task:Järjestys
Sender:cattes
Submission time:2016-10-08 23:19:51 +0300
Language:C++
Status:READY
Result:56
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED37
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s2details
#30.45 s3details

Code

#include <iostream>
#include <string.h>

void swap(int * buf, int swapcount) {
	int * swapped = new int[swapcount];
	for (int i = 0; i < swapcount; i++) {
		swapped[i] = buf[swapcount - 1 - i];
	}
	memcpy(buf, swapped, swapcount * 4);
}

int search(int * buf, int buflen, int searchfor) {
	for (int i = 0; i < buflen; i++) {
		if (buf[i] == searchfor) {
			return i;
		}
	}
	return -1;
}

int main() {
	
	int tableSize;

	std::cin >> tableSize;
	std::cin.get();

	int * table = new int[tableSize];

	for (int i = 0; i < tableSize; i++) {
		std::cin >> table[i];
	}
	std::cin.get();

	//do the thing
	int * swaps = new int[500000];
	int swapcount = 0;

	for (int i = 0; i < tableSize; i++) {
		int found = search(table, tableSize, tableSize-i);
		if (found != tableSize - 1 - i) {
			swap(table, found + 1);
			swap(table, tableSize - i);
			//record the swaps
			swaps[swapcount] = found + 1;
			swaps[swapcount + 1] = tableSize - i;
			swapcount = swapcount + 2;
		}
	}

	std::cout << swapcount << "\n";
	for (int i = 0; i < swapcount; i++) {
		std::cout << swaps[i] << " ";
	}
	std::cout << "\n";



	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
12
7 10 4 9 7 8 4 7 3 4 1 2 

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
1984
6 1000 904 999 964 998 333 997...

Test 3

Group: 3

Verdict:

input
100000
94703 47808 62366 31885 7091 8...

correct output
399956
98676 98676 98675 98676 62994 ...

user output
(empty)