Järjestys

#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);
	delete[] swapped;
}

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

int search2(int * initialPositions, int * swaphistory, int swapcount, int searchFor) {
	int pos = initialPositions[searchFor - 1];
	for (int i = 0; i < swapcount; i++) {
		if (swaphistory[i]-1 >= pos) {
			pos = swaphistory[i]-1 - pos;
		}
	}
	return pos;
}

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();

	/*int tableSize = 100000;
	int * table = new int[tableSize];
	for (int i = 0; i < tableSize; i++) {
		table[i] = i + 1;
	}*/

	
	//cache initial position of each number
	int * numPositions = new int[tableSize];
	for (int i = 0; i < tableSize; i++) {
		numPositions[table[i]-1] = i;
	}
	//numPositions[num-1] contains the position of num

	int * swaps = new int[1000000];
	int swapcount = 0;


	for (int i = 0; i < tableSize; i++) {
		//int found = search(table, tableSize, tableSize-i);
		int found = search2(numPositions, swaps, swapcount, 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 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED