CSES - Datatähti Open 2017 - Results
Submission details
Task:Witch game
Sender:NF
Submission time:2017-01-20 18:59:16 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.04 s1details
#2ACCEPTED0.04 s1details
#3ACCEPTED0.04 s1details
#40.04 s1details
#50.06 s1details
#60.04 s2details
#70.04 s2details
#80.45 s2details
#90.04 s2details
#100.04 s2details
#110.09 s3details
#120.11 s3details
#13--3details
#140.10 s3details
#150.11 s3details

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#define long long long

using namespace std;

int N;
int acc[100001];
set<int> adj[100001];

int main() {
    ios_base::sync_with_stdio(false);

    cin >> N;
    for (int i = 0; i < N; i++) {
        int j;
        cin >> j;
        j--;
        adj[i].insert(j);
        adj[j].insert(i);
        acc[i] = j;
    }
    long total = N * (N-1) * (N-2) / 6;
    for (int i = 0; i < N; i++) {
        int j = acc[i];
        // cout << i+1 << " " << j+1 << ": " << N - adj[i] - adj[i] - 2 << "\n";
        vector<int> un;
        set_union(adj[i].begin(), adj[i].end(), adj[j].begin(), adj[j].end(), back_inserter(un));
        vector<int> in;
        set_intersection(adj[i].begin(), adj[i].end(), adj[j].begin(), adj[j].end(), back_inserter(in));
        total -= N - un.size();
        // cout << i << " " << j << ": " << un.size() << "\n";
        if (adj[i].size() > 1) total -= (adj[i].size() * (adj[i].size() - 1) / 2);
        total -= in.size();
    }
    cout << total << "\n";
    return 0;
}

Test details

Test 1

Group: 1

Verdict:

input
100
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
156800

user output
151900

Test 2

Group: 1

Verdict: ACCEPTED

input
100
2 3 4 5 6 7 8 9 10 11 12 13 14...

correct output
152000

user output
152000

Test 3

Group: 1

Verdict: ACCEPTED

input
100
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
156849

user output
156849

Test 4

Group: 1

Verdict:

input
100
2 3 1 5 6 4 8 9 7 11 12 10 14 ...

correct output
151968

user output
151803

Test 5

Group: 1

Verdict:

input
100
8 98 100 62 42 36 95 70 22 49 ...

correct output
152040

user output
152035

Test 6

Group: 2

Verdict:

input
5000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
20808340000

user output
36836402

Test 7

Group: 2

Verdict:

input
5000
2 3 4 5 6 7 8 9 10 11 12 13 14...

correct output
20795850000

user output
36841402

Test 8

Group: 2

Verdict:

input
5000
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
20808342499

user output
49333901

Test 9

Group: 2

Verdict:

input
5000
2 3 1 5 6 4 8 9 7 11 12 10 14 ...

correct output
20795848337

user output
36831409

Test 10

Group: 2

Verdict:

input
5000
283 2880 2565 3289 4160 936 39...

correct output
20795852465

user output
36843867

Test 11

Group: 3

Verdict:

input
100000
2 1 4 3 6 5 8 7 10 9 12 11 14 ...

correct output
166656666800000

user output
-10244053984

Test 12

Group: 3

Verdict:

input
100000
2 3 4 5 6 7 8 9 10 11 12 13 14...

correct output
166651667000000

user output
-10243953984

Test 13

Group: 3

Verdict:

input
100000
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
166656666849999

user output
(empty)

Test 14

Group: 3

Verdict:

input
100000
2 3 1 5 6 4 8 9 7 11 12 10 14 ...

correct output
166651666966668

user output
-10244153981

Test 15

Group: 3

Verdict:

input
100000
186 62491 95379 37431 88427 93...

correct output
166651667250100

user output
-10243903881