Submission #1212248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212248		loom	Magic Show (APIO24_show)	C++20	35 / 100	2 ms	384 KiB

Alice

#include "Alice.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'

vector<pair<int,int>> Alice(){
   int n = 5000;
	int x = setN(n);
   int a = (x+n-1)/n;
   int b = x % n == 0 ? n : x % n;
   int c = (a+b) % n;
   
   vector<pair<int,int>> g;

   int cnt = 0, p, q, r;
   for(int i=1; i<=n; i++){
      if(i == a or i == b or i == c) continue;
      cnt++;
      if(cnt <= 1666) g.push_back({a, i}), p = i;
      else if(cnt <= 3331) g.push_back({b, i}), q = i;
      else g.push_back({c, i}), r = i;
   }

   g.push_back({p, q});
   g.push_back({q, r});

   return g;
}

Bob

#include "Bob.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'

ll Bob(vector<pair<int,int>> v){
   int n = 5000;
   vector<int> deg(n+1), ch(n+1);

   for(auto [a, b] : v){
      if(deg[a] == 0) ch[a] = b;
      if(deg[b] == 0) ch[b] = a;
      deg[a]++;
      deg[b]++;
   }

   int p = -1, q;
   for(int i=1; i<=n; i++){
      if(deg[i] <= 10) continue;
      if(p == -1) p = i;
      else{
         q = i;
         break;
      }
   }

   int x = -1, y = -1, sum = -1;

   int pc = ch[p];
   if(pc <= 1666) x = p;
   else if(pc <= 3331) y = p;
   else sum = p;

   int qc = ch[q];
   if(qc <= 1666) x = q;
   else if(qc <= 3331) y = q;
   else sum = q;

   if(x == -1) x = (sum - y + n) % n;
   else if(y == -1) y = (sum - x + n) % n;

   return (x-1) * n + y;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65