oj.uz

Submission #470106

# Submission time Handle Problem Language Result Execution time Memory
470106 2021-09-03T02:50:35 Z dantoh000 Cat (info1cup19_cat) C++14
40 / 100
 362 ms 1868 KB 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        int n;
        scanf("%d",&n);
        vector<int> a(n+1,0);
        vector<int> vis(n/2+1,0);
        vector<int> marked(n/2+1,0);
        for (int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
        }
        bool can = true;
        int sw = 0;
        int extra = 0;
        int hmm = 0;
        for (int i = 1; i <= n/2; i++){
            if (a[i]+a[n+1-i] != n+1) can = false;
            if (a[i] > n/2){
                sw++;
                marked[i] = 1;
                a[i] = n+1-a[i];
            }
        }
        if (sw % 2 != 0) can = false;
        if (!can){
            printf("-1\n");
            continue;
        }
        int ans = 0;
        for (int i = 1; i <= n/2; i++){
            //printf("%d ",a[i]);
            if (vis[i] == 0){

                int ct = 0;
                vis[i] = 1;
                ct += marked[i];
                int len = 1;
                int cur = a[i];
                while (cur != i){
                    ct += marked[cur];
                    len++;
                    vis[cur] = 1;
                    cur = a[cur];
                }
                //printf("ct = %d len = %d\n",ct,len);
                if (ct % 2 == 0){
                    ans += len-1;
                }
                else{
                    ans += len;
                }
            }
        }
        printf("%d 0\n",ans);


    }


}

Compilation message

cat.cpp: In function 'int main()':
cat.cpp:17:13: warning: unused variable 'extra' [-Wunused-variable]
   17 |         int extra = 0;
      |             ^~~~~
cat.cpp:18:13: warning: unused variable 'hmm' [-Wunused-variable]
   18 |         int hmm = 0;
      |             ^~~
cat.cpp:5:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~
cat.cpp:8:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
cat.cpp:13:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |             scanf("%d",&a[i]);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correct number of moves

Subtask #2
4.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 312 KB Correct number of moves
2 Correct 19 ms 332 KB Correct number of moves

Subtask #3
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correct number of moves
2 Correct 19 ms 312 KB Correct number of moves
3 Correct 19 ms 332 KB Correct number of moves
4 Correct 19 ms 204 KB Correct number of moves
5 Correct 8 ms 332 KB Correct number of moves
6 Correct 9 ms 204 KB Correct number of moves

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 312 KB Correct number of moves
2 Correct 19 ms 332 KB Correct number of moves
3 Correct 323 ms 980 KB Correct number of moves
4 Correct 335 ms 1328 KB Correct number of moves
5 Correct 333 ms 1712 KB Correct number of moves

Subtask #5
14.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correct number of moves
2 Correct 19 ms 312 KB Correct number of moves
3 Correct 19 ms 332 KB Correct number of moves
4 Correct 19 ms 204 KB Correct number of moves
5 Correct 8 ms 332 KB Correct number of moves
6 Correct 9 ms 204 KB Correct number of moves
7 Correct 323 ms 980 KB Correct number of moves
8 Correct 335 ms 1328 KB Correct number of moves
9 Correct 333 ms 1712 KB Correct number of moves
10 Correct 338 ms 620 KB Correct number of moves
11 Correct 326 ms 792 KB Correct number of moves
12 Correct 350 ms 1868 KB Correct number of moves
13 Correct 362 ms 1744 KB Correct number of moves
14 Correct 356 ms 1688 KB Correct number of moves