Task: | Järjestys |
Sender: | kapesu8 |
Submission time: | 2016-10-14 13:08:23 +0300 |
Language: | C++ |
Status: | READY |
Result: | 56 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 19 |
#2 | ACCEPTED | 37 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.05 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 2 | details |
#3 | WRONG ANSWER | 0.11 s | 3 | details |
Code
#include <iostream>#include <string>#include <cstdio>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_list_size = 0;int *numbers = new int[count+1];int *numbers_i = new int[count+1];int *klist = new int[count*5];int klist_top = 0;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) //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;numbers_list_size++;current_index = numbers[current_index];if(current_index == 1)break;}//search first where numbers_list[i] != true && numbers[i] != iint numbers_list2_i1 = 0;int numbers_list2_in = 0;for(int i = 1;i <= count;i++){if(!numbers_list[i] && !(numbers[i] == i)){numbers_list2_i1 = i;break;}}if(numbers_list2_i1 != 0){//search last (numbers_list2_in) in linked sequencecurrent_index = numbers[numbers_list2_i1];while(numbers[current_index] != numbers_list2_i1){current_index = numbers[current_index];}numbers_list2_in = current_index;//swap numbers_list2_in and numbers_i[1] (6 reversals)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}//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::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: WRONG ANSWER
input |
---|
100000 94703 47808 62366 31885 7091 8... |
correct output |
---|
399956 98676 98676 98675 98676 62994 ... |
user output |
---|
334716 51654 31705 31704 31705 31706 ... |