Submission #1079068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079068		Hanksburger	Magic Show (APIO24_show)	C++17	35 / 100	3 ms	1332 KiB

Alice

#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()
{
    int 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;
}

Bob

#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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65