oj.uz

Submission #470098

# Submission time Handle Problem Language Result Execution time Memory
470098 2021-09-03T01:53:13 Z dantoh000 Cat (info1cup19_cat) C++14
21.25 / 100
 369 ms 1840 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 (a[i] == i) hmm++;
            }
        }
        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{
                    if (len == 1 && ct == 1) continue;
                    ans += len;
                    extra ++;
                }

            }
        }
        ans -= extra/2;
        ans += hmm/2;
        if (hmm % 2 == 1) ans++;

        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 6 ms 204 KB Correctly distinguished between possibility and impossibility

Subtask #2
4.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 308 KB Correct number of moves
2 Correct 18 ms 300 KB Correct number of moves

Subtask #3
3.75 / 25.0

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

Subtask #4
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 308 KB Correct number of moves
2 Correct 18 ms 300 KB Correct number of moves
3 Correct 324 ms 1072 KB Correct number of moves
4 Correct 341 ms 1308 KB Correct number of moves
5 Correct 323 ms 1724 KB Correct number of moves

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 25 ms 308 KB Correct number of moves
3 Correct 18 ms 300 KB Correct number of moves
4 Correct 18 ms 308 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 332 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 204 KB Correctly distinguished between possibility and impossibility
7 Correct 324 ms 1072 KB Correct number of moves
8 Correct 341 ms 1308 KB Correct number of moves
9 Correct 323 ms 1724 KB Correct number of moves
10 Correct 369 ms 608 KB Correctly distinguished between possibility and impossibility
11 Correct 341 ms 764 KB Correctly distinguished between possibility and impossibility
12 Correct 342 ms 1840 KB Correctly distinguished between possibility and impossibility
13 Correct 345 ms 1752 KB Correctly distinguished between possibility and impossibility
14 Correct 348 ms 1808 KB Correctly distinguished between possibility and impossibility