Submission #26621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26621	2017-07-03T13:20:32 Z	model_code	Shift (POI11_prz)	C++11	87 / 100	1000 ms	7420 KB

/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Przekladanka                                     *
 *   Autor:             Jacek Migdal                                     *
 *   Zlozonosc czasowa: O(n^3)                                           *
 *   Opis:              Rozwiazanie powolne                              *
 *                                                                       *
 *************************************************************************/

#include <list>
#include <vector>
#include <cstdio>

using namespace std;

vector<int> answer;
vector<int> data;

void addAnswer(int num)
{
    if (!answer.empty() && answer.back() * num > 0) {
        answer.back() += num;
    } else {
        answer.push_back(num);
    }
}

void operationPlus() {
    data.insert(data.begin(), data.back());
    data.pop_back();
    addAnswer(1);
}

void operationPlus2() {
    data.push_back(data.front());
    data.erase(data.begin());
    addAnswer(((int) data.size()) - 1);
}

void operationMinus() {
    int a = *(++(++data.begin()));
    data.erase(++(++data.begin()));
    data.insert(data.begin(), a);
    addAnswer(-1);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0 ; i< n ; ++i) {
        int a;
        scanf("%d", &a);
        data.push_back(a);
    }

    if (n <= 2) {
        if (n == 1 || 1 == *data.begin()) {
            printf("0\n");
        } else {
            printf("1\n1a\n");
        }
        return 0;
    }

    for (int j = 2 ; j <= (n - 2) ; ++j) {
        while (data.front() != j) {
            operationPlus();
        }

        while (data.back() != j - 1) {
            operationPlus();
            if (data.back() != j - 1) {
                operationPlus();
                operationMinus();
            } else {
                operationMinus();
                operationMinus();
            }
        }
    }

    while (data.front() != 1) {
        operationPlus();
    }

    if (data.back() != n) {
        if (n % 2 == 1) {
            printf("NIE DA SIE\n");
            return 0;
        } else {
            operationPlus();

            while (*(++data.begin()) != n) {
                operationMinus();
                operationMinus();
                operationPlus2();
                operationPlus2();
            }
            for (int i = 0 ; i < n - 2 ; ++i) {
                operationPlus();
            }
        }
    }

    int nonZeroAns = 0;
    for(unsigned int i = 0; i < answer.size(); ++i) {
        if (answer[i] % n != 0) nonZeroAns++;
    }
    printf("%d\n",nonZeroAns);

    for (unsigned int i = 0 ; i < answer.size() ; ++i) {
        if (answer[i] % n != 0) {
            int x = answer[i] % n;
            if (x > 0) {
                printf("%da ",x);
            } else {
                printf("%db ", x * (-1));
            }
        }
    }
    return 0;
}

Compilation message

prz.cpp: In function 'int main()':
prz.cpp:52:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
prz.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
                        ^

Subtask #1
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct
4	Correct	1176 KB	Output is correct
5	Correct	1176 KB	Output is correct
6	Correct	1176 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	1176 KB	Output is correct
2	Correct	1176 KB	Output is correct
3	Correct	1176 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1316 KB	Output is correct
2	Correct	0 ms	1316 KB	Output is correct
3	Correct	0 ms	1316 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	1648 KB	Output is correct
2	Correct	29 ms	1648 KB	Output is correct
3	Correct	23 ms	1648 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	623 ms	7420 KB	Output is correct
2	Correct	619 ms	7420 KB	Output is correct
3	Correct	623 ms	7420 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	769 ms	7420 KB	Output is correct
2	Correct	776 ms	7420 KB	Output is correct
3	Correct	726 ms	7420 KB	Output is correct

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	926 ms	7420 KB	Output is correct
2	Execution timed out	1000 ms	7420 KB	Execution timed out
3	Halted	0 ms	0 KB	-