oj.uz

Submission #470097

# Submission time Handle Problem Language Result Execution time Memory
470097 2021-09-03T01:49:46 Z dantoh000 Cat (info1cup19_cat) C++14
21.25 / 100
 373 ms 1952 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;
        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;
                    if (len != 1) extra++;
                }

            }
        }
        ans -= extra/2;

        printf("%d 0\n",ans);


    }


}

Compilation message

cat.cpp: In function 'int main()':
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
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correctly distinguished between possibility and impossibility

Subtask #2
4.0 / 10.0

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

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 19 ms 332 KB Correct number of moves
3 Correct 18 ms 332 KB Correct number of moves
4 Correct 21 ms 316 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 332 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 300 KB Correctly distinguished between possibility and impossibility

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 332 KB Correct number of moves
2 Correct 18 ms 332 KB Correct number of moves
3 Correct 328 ms 1120 KB Correct number of moves
4 Correct 335 ms 1432 KB Correct number of moves
5 Correct 331 ms 1776 KB Correct number of moves

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 19 ms 332 KB Correct number of moves
3 Correct 18 ms 332 KB Correct number of moves
4 Correct 21 ms 316 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 332 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 300 KB Correctly distinguished between possibility and impossibility
7 Correct 328 ms 1120 KB Correct number of moves
8 Correct 335 ms 1432 KB Correct number of moves
9 Correct 331 ms 1776 KB Correct number of moves
10 Correct 350 ms 828 KB Correctly distinguished between possibility and impossibility
11 Correct 337 ms 1068 KB Correctly distinguished between possibility and impossibility
12 Correct 349 ms 1924 KB Correctly distinguished between possibility and impossibility
13 Correct 373 ms 1832 KB Correctly distinguished between possibility and impossibility
14 Correct 357 ms 1952 KB Correctly distinguished between possibility and impossibility