oj.uz

Submission #1079073

# Submission time Handle Problem Language Result Execution time Memory
1079073 2024-08-28T10:24:38 Z Hanksburger Magic Show (APIO24_show) C++17
100 / 100
 3 ms 1328 KB 
#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> added[21], special, vec, cur;
long long fac[20], a[21], b[21];
vector<pair<int, int> > ans;
vector<pair<int, int> > Alice()
{
    long long x=setN(4998);
    srand(time(0));
    for (int i=0; i<21; i++)
        special.push_back(rand()%238*21+i);
    for (int i=0; i<4998; i++)
    {
        if (special[i%21]==i)
            continue;
        vec.push_back(i);
    }
    random_shuffle(vec.begin(), vec.end());
    fac[0]=1;
    for (int i=1; i<20; i++)
        fac[i]=fac[i-1]*i;
    for (int i=1; i<21; i++)
        cur.push_back(i);
    for (int i=1; i<21; i++)
    {
        int ind=x/fac[20-i];
        x%=fac[20-i];
        a[i]=cur[ind];
        b[cur[ind]]=i;
        cur.erase(cur.begin()+ind);
    }
    for (int i=0; i<20; i++)
        ans.push_back({special[a[i]]+1, special[a[i+1]]+1});
    for (int i=0; i<21; i++)
        added[i].push_back(special[i]);
    for (int i=0; i<vec.size(); i++)
    {
        int num=vec[i];
        int pos=b[num%21];
        int target=a[(pos==20?19:pos+1)];
        int ran=rand()%added[target].size();
        ans.push_back({num+1, added[target][ran]+1});
        added[num%21].push_back(num);
    }
    return ans;
}
#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;
int arr[21], brr[21], taken[21];
vector<int> adj[21];
long long fact[20];
long long Bob(vector<pair<int, int> > edge)
{
    for (int i=0; i<edge.size(); i++)
    {
        edge[i].first--;
        edge[i].second--;
        adj[edge[i].first%21].push_back(edge[i].second%21);
        adj[edge[i].second%21].push_back(edge[i].first%21);
    }
    for (int i=0; i<21; i++)
    {
        sort(adj[i].begin(), adj[i].end());
        adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
    }
    fact[0]=1;
    for (int i=1; i<20; i++)
        fact[i]=fact[i-1]*i;
    for (int i=1; i<21; i++)
    {
        if (adj[arr[i-1]].size()==1)
            arr[i]=adj[arr[i-1]][0];
        else if (adj[arr[i-1]][0]==arr[i-2])
            arr[i]=adj[arr[i-1]][1];
        else
            arr[i]=adj[arr[i-1]][0];
    }
    for (int i=0; i<21; i++)
    {
        int cnt=0;
        for (int j=0; j<arr[i]; j++)
            if (taken[j])
                cnt++;
        brr[i]=arr[i]-cnt;
        taken[arr[i]]=1;
    }
    long long res=0;
    for (int i=1; i<21; i++)
        res+=brr[i]*fact[20-i];
    return res;
}

Compilation message

Alice.cpp: In function 'std::vector<std::pair<int, int> > Alice()':
Alice.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0; i<vec.size(); i++)
      |                   ~^~~~~~~~~~~

Bob.cpp: In function 'long long int Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<edge.size(); i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Correct 3 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1068 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1076 KB Correct.
7 Correct 2 ms 1076 KB Correct.
8 Correct 2 ms 1080 KB Correct.
9 Correct 2 ms 1088 KB Correct.
10 Correct 1 ms 1024 KB Correct.
11 Correct 2 ms 1076 KB Correct.
12 Correct 1 ms 1080 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Correct 3 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1068 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1076 KB Correct.
7 Correct 2 ms 1076 KB Correct.
8 Correct 2 ms 1080 KB Correct.
9 Correct 2 ms 1088 KB Correct.
10 Correct 1 ms 1024 KB Correct.
11 Correct 2 ms 1076 KB Correct.
12 Correct 1 ms 1080 KB Correct.
13 Correct 2 ms 1076 KB Correct.
14 Correct 2 ms 1076 KB Correct.
15 Correct 2 ms 1076 KB Correct.
16 Correct 2 ms 1092 KB Correct.
17 Correct 2 ms 1076 KB Correct.
18 Correct 1 ms 1080 KB Correct.
19 Correct 2 ms 1088 KB Correct.
20 Correct 1 ms 1088 KB Correct.
21 Correct 2 ms 1076 KB Correct.
22 Correct 3 ms 1084 KB Correct.
23 Correct 1 ms 1076 KB Correct.
24 Correct 1 ms 1088 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Correct 3 ms 1076 KB Correct.
3 Correct 1 ms 1076 KB Correct.
4 Correct 2 ms 1068 KB Correct.
5 Correct 2 ms 1076 KB Correct.
6 Correct 2 ms 1076 KB Correct.
7 Correct 2 ms 1076 KB Correct.
8 Correct 2 ms 1080 KB Correct.
9 Correct 2 ms 1088 KB Correct.
10 Correct 1 ms 1024 KB Correct.
11 Correct 2 ms 1076 KB Correct.
12 Correct 1 ms 1080 KB Correct.
13 Correct 2 ms 1076 KB Correct.
14 Correct 2 ms 1076 KB Correct.
15 Correct 2 ms 1076 KB Correct.
16 Correct 2 ms 1092 KB Correct.
17 Correct 2 ms 1076 KB Correct.
18 Correct 1 ms 1080 KB Correct.
19 Correct 2 ms 1088 KB Correct.
20 Correct 1 ms 1088 KB Correct.
21 Correct 2 ms 1076 KB Correct.
22 Correct 3 ms 1084 KB Correct.
23 Correct 1 ms 1076 KB Correct.
24 Correct 1 ms 1088 KB Correct.
25 Correct 2 ms 1076 KB Correct.
26 Correct 3 ms 1076 KB Correct.
27 Correct 2 ms 1080 KB Correct.
28 Correct 2 ms 1088 KB Correct.
29 Correct 2 ms 1076 KB Correct.
30 Correct 2 ms 1076 KB Correct.
31 Correct 1 ms 1088 KB Correct.
32 Correct 1 ms 1076 KB Correct.
33 Correct 1 ms 1076 KB Correct.
34 Correct 2 ms 1076 KB Correct.
35 Correct 2 ms 1328 KB Correct.
36 Correct 2 ms 1072 KB Correct.
37 Correct 1 ms 1088 KB Correct.
38 Correct 2 ms 1180 KB Correct.
39 Correct 2 ms 1072 KB Correct.
40 Correct 2 ms 1076 KB Correct.
41 Correct 2 ms 1080 KB Correct.
42 Correct 1 ms 1072 KB Correct.
43 Correct 2 ms 1076 KB Correct.
44 Correct 2 ms 1076 KB Correct.