Submission #606999

#	Time	Username	Problem	Language	Result	Execution time	Memory
606999		1bin	Shift (POI11_prz)	C++14	100 / 100	178 ms	14284 KiB

prz

    #include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e3 + 5;
int n, a[NMAX], ix[NMAX], cnt, s, x;
vector<int> v;

void flsh(){
    v.emplace_back(1);
    v.emplace_back(3);
    v.emplace_back(n - 1);
}

void move(int x, int cnt){
    while(cnt){
        if(cnt == 1) {
            if(ix[a[x]] == 1) flsh();
            else v.emplace_back((-ix[a[x]] + 1 + n) % n);
            
            swap(a[x - 1], a[x]);
            swap(a[x], a[x + 1]);
            cnt--; ix[a[x]] = 0;
            v.emplace_back(2);
        }
        else{
            if(ix[a[x]] == 2) flsh();
            else v.emplace_back((-ix[a[x]] + 2 + n) % n);
            swap(a[x - 1], a[x]); x--;
            swap(a[x - 1], a[x]); x--;
            cnt -= 2; ix[a[x]] = 0;
            v.emplace_back(1);
        }
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i]; a[i]--;
        for(int j = 0; j < i; j++) 
            if(a[j] > a[i]) cnt++;
    }
    
    if(n == 2) {
        if(a[0] == 1) cout << "1\n1a";
        else cout << 0;
    }
    else if(n & 1 && cnt & 1) cout << "NIE DA SIE";
    else{
        if(cnt & 1) {
            x = a[n - 1];
            for(int i = n - 1; i; i--) a[i] = a[i - 1];
            a[0] = x;
            v.emplace_back(1);
            v.emplace_back(3);
        }
        
        for(int i = 0; i < n; i++) ix[a[i]] = i;
        for(int i = 0; i < n; i++){
            if(a[i] == i) continue;
            
            for(int j = 0; j < n; j++) 
                if(a[j] == i) move(j, j - i);
            for(int j = 0; j < n; j++) ix[a[j]] = (j + n - i) % n; 
            
        }
        if(ix[0]) v.emplace_back(n - ix[0]);
        
        cout << v.size() << '\n';
        for(int i = 0; i < v.size(); i++){
            if(i & 1) cout << v[i] << "b ";
            else cout << v[i] << "a ";
        }
    }
    return 0;
}

Compilation message (stderr)

prz.cpp: In function 'int main()':
prz.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i = 0; i < v.size(); i++){
      |                        ~~^~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13