QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#101582	#5526. Jewel of Data Structure Problems	Liberty12619	WA	45ms	3776kb	C++20	1.3kb	2023-04-30 13:32:43	2023-04-30 13:32:47

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-30 13:32:47]
评测

测评结果：WA
用时：45ms
内存：3776kb

查看

[2023-04-30 13:32:43]
提交

answer

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5+10,mod = 998244353;
typedef pair<int,int>PII;

bool st[N],a[N],p[N];
void dfs(int u)
{
    st[u]=true;
    if(!st[p[u]])dfs(p[u]);
}

void solve()
{
    int n,m;
    cin>>n>>m;
    int odd_cnt=0,status=0,in_cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&p[i]);
        odd_cnt+=i+p[i]&1;
        in_cnt+=i!=p[i];
    }
    status = n&1;
    for(int i=1;i<=n;i++)
        if(!st[i])
        {
            dfs(i);
            status^=1;
        }
    while(m--)
    {
        int u,v;
        scanf("%lld %lld",&u,&v);
        if(p[u]+u&1)    odd_cnt--;
        if(p[v]+v&1)    odd_cnt--;
        if(p[u]!=u)     in_cnt--;
        if(p[v]!=v)     in_cnt--;
        swap(p[u],p[v]);
        if(p[u]+u&1)    odd_cnt++;
        if(p[v]+v&1)    odd_cnt++;
        if(p[u]!=u)     in_cnt++;
        if(p[v]!=v)     in_cnt++;
        status^=1;
        if(status)  printf("%lld\n",n);
        else if(odd_cnt) printf("%lld\n",n-1);
        else if(in_cnt) printf("%lld\n",n-2);
        else    puts("-1");
    }
    
}
signed main()
{
    int T =1 ;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3588kb

input:

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 26ms

memory: 3512kb

input:

output:

2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
2
-1
...

result:

ok 200000 numbers

Test #3:

score: 0

Accepted

time: 37ms

memory: 3768kb

input:

output:

result:

ok 200000 numbers

Test #4:

score: 0

Accepted

time: 34ms

memory: 3592kb

input:

output:

result:

ok 200000 numbers

Test #5:

score: 0

Accepted

time: 36ms

memory: 3516kb

input:

output:

result:

ok 200000 numbers

Test #6:

score: 0

Accepted

time: 16ms

memory: 3528kb

input:

6 200000
4 2 5 3 6 1
1 2
4 6
5 4
1 6
6 5
4 2
5 3
6 2
6 5
1 4
6 3
6 5
2 3
4 5
4 1
3 6
5 6
2 4
3 2
2 3
6 1
1 3
1 3
3 6
1 6
2 5
3 4
1 4
4 1
4 6
3 5
6 2
6 5
4 1
5 6
5 4
1 6
2 4
6 3
1 3
5 2
1 6
1 3
1 3
3 6
6 5
3 2
6 4
6 4
3 2
3 1
5 3
6 3
6 5
3 5
2 5
4 2
1 5
1 2
3 4
3 2
4 6
3 5
2 1
5 4
1 4
5 3
1 5
5 4
3 1...

output:

result:

ok 200000 numbers

Test #7:

score: 0

Accepted

time: 32ms

memory: 3584kb

input:

7 200000
6 1 3 4 5 2 7
7 4
5 2
6 1
3 4
3 1
5 3
7 2
6 4
2 5
5 6
6 2
1 7
3 4
6 2
7 4
3 1
4 5
5 6
6 3
4 1
6 1
7 1
5 7
1 3
4 1
5 4
5 7
2 1
6 4
7 5
3 1
4 1
4 2
4 3
5 6
4 2
1 6
3 2
2 6
3 4
1 6
4 5
1 2
1 5
3 1
4 6
3 4
1 4
7 5
2 7
2 5
1 7
3 2
3 5
2 5
6 2
6 7
1 2
2 7
1 2
3 1
1 4
5 2
6 4
6 1
3 6
6 4
4 2
6 2
2...

output:

result:

ok 200000 numbers

Test #8:

score: 0

Accepted

time: 26ms

memory: 3524kb

input:

8 200000
5 4 7 1 6 2 8 3
8 4
5 3
2 6
5 3
3 5
1 6
3 4
5 3
1 3
1 2
6 3
8 7
8 3
3 8
6 4
3 4
3 7
6 4
4 2
7 3
4 8
7 8
8 5
4 3
8 1
1 2
2 1
6 5
7 2
7 1
6 1
3 6
6 1
6 1
7 1
7 3
2 3
3 7
4 7
8 5
3 1
2 7
2 3
4 5
3 2
4 6
4 8
4 6
8 1
1 2
8 6
5 6
7 2
6 7
5 8
4 2
6 3
6 3
8 3
6 7
8 7
8 2
6 8
1 4
5 1
2 3
4 6
7 5
8 4...

output:

result:

ok 200000 numbers

Test #9:

score: 0

Accepted

time: 38ms

memory: 3528kb

input:

9 200000
4 3 8 9 2 1 7 5 6
9 6
1 6
4 1
7 3
7 9
5 8
6 2
1 4
2 3
3 8
5 8
7 4
6 4
3 7
9 8
3 8
9 5
9 3
6 3
7 8
1 6
1 9
2 3
7 6
9 1
9 5
1 6
9 7
6 7
3 5
6 7
5 7
7 6
2 6
2 6
8 4
2 8
3 9
5 8
3 9
6 2
6 9
8 5
2 5
6 5
8 5
6 2
1 5
7 6
6 9
2 8
6 9
2 5
8 9
6 8
2 5
1 7
3 2
9 1
6 7
8 9
3 7
5 3
4 7
7 2
8 2
2 3
8 2
6...

output:

result:

ok 200000 numbers

Test #10:

score: 0

Accepted

time: 36ms

memory: 3512kb

input:

10 200000
7 10 4 9 1 6 2 3 5 8
4 9
8 7
2 3
6 10
4 5
7 6
5 6
2 6
10 1
7 5
9 10
8 9
6 9
8 5
2 3
5 1
5 7
5 4
1 9
7 4
2 7
8 6
3 10
1 2
4 1
1 5
5 8
5 7
10 3
2 7
1 5
8 10
10 6
8 10
10 4
1 10
5 4
5 10
2 10
6 5
8 6
8 1
8 9
2 4
4 2
10 9
9 8
2 8
4 1
7 10
9 7
10 9
7 3
2 6
4 8
5 9
6 9
1 2
1 5
10 6
1 2
5 10
10 7...

output:

result:

ok 200000 numbers

Test #11:

score: 0

Accepted

time: 41ms

memory: 3608kb

input:

1000 200000
82 684 685 362 991 147 175 795 885 927 938 576 958 210 494 72 823 989 662 585 461 853 955 282 310 348 861 735 249 988 994 923 513 153 496 598 776 273 965 587 833 157 244 722 30 102 935 571 432 488 211 624 121 302 867 57 588 106 901 393 394 626 363 70 887 331 870 83 708 891 46 275 193 702...

output:

result:

ok 200000 numbers

Test #12:

score: -100

Wrong Answer

time: 45ms

memory: 3776kb

input:

1000 200000
828 824 777 731 21 589 502 672 335 762 265 349 612 24 17 713 753 324 751 69 827 579 505 469 495 846 245 382 439 415 741 169 30 347 199 730 422 742 810 97 645 253 1 372 926 865 852 629 215 2 187 340 791 362 554 802 452 685 866 370 584 592 19 100 522 350 847 702 473 33 927 102 430 296 755 ...

output:

result:

wrong answer 1st numbers differ - expected: '1000', found: '999'