Submission #26618

# Submission time Handle Problem Language Result Execution time Memory
26618 2017-07-03T13:19:14 Z model_code Shift (POI11_prz) C++11
61 / 100
1000 ms 7468 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;
list<int> data;

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

void operationPlus() {
    data.push_front(data.back());
    data.pop_back();
    addAnswer(1);
}

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

void operationMinus() {
    int a = *(++(++data.begin()));
    data.remove(a);
    data.push_front(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));
            }
        }
    }
    printf("\n");

    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);
                        ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Output is correct
3 Correct 0 ms 1176 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 3 ms 1176 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Output is correct
3 Correct 0 ms 1176 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Output is correct
3 Correct 0 ms 1176 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 1324 KB Output is correct
2 Correct 3 ms 1324 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 46 ms 1660 KB Output is correct
2 Correct 43 ms 1660 KB Output is correct
3 Correct 46 ms 1660 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 7456 KB Execution timed out
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 7460 KB Execution timed out
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 7468 KB Execution timed out
2 Halted 0 ms 0 KB -