oj.uz

Submission #288108

# Submission time Handle Problem Language Result Execution time Memory
288108 2020-09-01T08:48:21 Z 반딧불(#5783) JOIRIS (JOI16_joiris) C++17
15 / 100
 429 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;
int arr[52];
vector<pair<int, int> > ans;
bool chk[52];

bool allSame(){
    for(int i=1; i<=n; i++) if(arr[i]) return false;
    return true;
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
    }

    if(n%2==0){
        int tmp = 0;
        for(int i=1; i<=n; i++){
            tmp += arr[i];
        }
        if(tmp%2){
            printf("-1");
            return 0;
        }
    }

    int topElem = *max_element(arr+1, arr+n+1);
    for(int i=1; i<=n; i++){
        while(arr[i] < topElem - 1){
            arr[i] += 2;
            ans.push_back({1, i});
        }
    }

    int bottom = *min_element(arr+1, arr+n+1);
    for(int i=1; i<=n; i++) arr[i] -= bottom;

    int cnt = 100;
    while(1){
//        for(int i=1; i<=n; i++) printf("%d ", arr[i]); puts("");
        bool hasChk = 0;

        if(allSame()) break;
        int pnt = 1e9;
        for(int i=n; i>=1; i--){
            if(!arr[i]){
                pnt = i;
                break;
            }
        }
        ans.push_back({1, pnt}), arr[pnt] += 2;

        for(int i=pnt+1; i<=n; i++){
            while(1){
                if(arr[i] >= 2) break;
                if(arr[i+1] >= 2 || i==n){
                    ans.push_back({1, i}), arr[i]+=2;
                    break;
                }
                ans.push_back({2, i});
                if(arr[i] < arr[i+1]) chk[i] = 1, hasChk = 1;
                if(arr[i] > arr[i+1]) chk[i+1] = 1, hasChk = 1;
                arr[i] = max(arr[i], arr[i+1]) + 1;
                arr[i+1] = arr[i];
            }
        }
        for(int i=pnt-1; i>=1; i--){
            while(1){
                if(arr[i] >= 2) break;
                if(arr[i-1] >= 2 || i==1){
                    ans.push_back({1, i}), arr[i]+=2;
                    break;
                }
                ans.push_back({2, i-1});
                if(arr[i] < arr[i-1]) chk[i] = 1, hasChk = 1;
                if(arr[i] > arr[i-1]) chk[i-1] = 1, hasChk = 1;
                arr[i] = max(arr[i], arr[i-1]) + 1;
                arr[i-1] = arr[i];
            }
        }

        int minElem = *min_element(arr+1, arr+n+1);
        if(hasChk) minElem--;
        for(int i=1; i<=n; i++){
            arr[i] -= minElem;
            if(chk[i]){
                chk[i] = 0;
                arr[i] = 0;
            }
        }
    }

    printf("%d\n", (int)ans.size());
    for(auto &x: ans){
        printf("%d %d\n", x.first, x.second);
    }
}

Compilation message

joiris.cpp: In function 'int main()':
joiris.cpp:45:9: warning: unused variable 'cnt' [-Wunused-variable]
   45 |     int cnt = 100;
      |         ^~~
joiris.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
joiris.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 429 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Incorrect 0 ms 256 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 0 ms 256 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Runtime error 429 ms 262148 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -