oj.uz

Submission #470099

# Submission time Handle Problem Language Result Execution time Memory
470099 2021-09-03T01:58:54 Z dantoh000 Cat (info1cup19_cat) C++14
21.25 / 100
 372 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 (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;
        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 5 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 204 KB Correct number of moves
2 Correct 18 ms 308 KB Correct number of moves

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 25 ms 204 KB Correct number of moves
3 Correct 18 ms 308 KB Correct number of moves
4 Correct 20 ms 204 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 336 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 204 KB Correct number of moves
2 Correct 18 ms 308 KB Correct number of moves
3 Correct 326 ms 1080 KB Correct number of moves
4 Correct 350 ms 1260 KB Correct number of moves
5 Correct 350 ms 1724 KB Correct number of moves

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 204 KB Correctly distinguished between possibility and impossibility
2 Correct 25 ms 204 KB Correct number of moves
3 Correct 18 ms 308 KB Correct number of moves
4 Correct 20 ms 204 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 336 KB Correctly distinguished between possibility and impossibility
6 Correct 6 ms 204 KB Correctly distinguished between possibility and impossibility
7 Correct 326 ms 1080 KB Correct number of moves
8 Correct 350 ms 1260 KB Correct number of moves
9 Correct 350 ms 1724 KB Correct number of moves
10 Correct 319 ms 716 KB Correctly distinguished between possibility and impossibility
11 Correct 321 ms 792 KB Correctly distinguished between possibility and impossibility
12 Correct 340 ms 1868 KB Correctly distinguished between possibility and impossibility
13 Correct 372 ms 1744 KB Correctly distinguished between possibility and impossibility
14 Correct 337 ms 1792 KB Correctly distinguished between possibility and impossibility