Submission #606999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
606999	2022-07-26T11:04:50 Z	1bin	Shift (POI11_prz)	C++14	100 / 100	178 ms	14284 KB

    #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

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	856 KB	Output is correct
2	Correct	7 ms	856 KB	Output is correct
3	Correct	8 ms	856 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	4844 KB	Output is correct
2	Correct	64 ms	4928 KB	Output is correct
3	Correct	62 ms	4784 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	6060 KB	Output is correct
2	Correct	78 ms	6024 KB	Output is correct
3	Correct	77 ms	5944 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	7224 KB	Output is correct
2	Correct	96 ms	7296 KB	Output is correct
3	Correct	178 ms	14284 KB	Output is correct
4	Correct	13 ms	340 KB	Output is correct
5	Correct	2 ms	212 KB	Output is correct