Submission #1218137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218137		urosk	Magic Show (APIO24_show)	C++20	0 / 100	2 ms	884 KiB

Alice

#include <vector>
#include "Alice.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#define pb push_back
#define si(a_) (ll)(a_.size())
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;

using ll = int;
using pll = pair<ll,ll>;

vector<pll> ans;
void upd(vector<pll> &v){
    for(auto &it : v) it.fi++,it.sc++;
}
std::vector<std::pair<int,int>> Alice(){
    ll n = 5000;
    long long x = setN(n);
    x--;
    ll a = x/n;
    ll b = x%n;
    a++;
    b++;
    ll c = a^b;
    //cerr<<"abc: "<<a<< " "<<b<< " "<<c<<endl;
    if(a==b){
        for(ll i = 1;i<=n;i++){
            if(i^a) ans.pb({i,a});
        }
        return ans;
    }
    ans.pb({a,c});
    ans.pb({b,c});
    vector<ll> v;
    for(ll i = 1;i<=n;i++){
        if(i!=a&&i!=b&&i!=c) v.pb(i);
    }
    ll l = si(v)/3,r = 2*si(v)/3;
    for(ll i = 0;i<l;i++) ans.pb({a,v[i]});
    for(ll i = l;i<r;i++) ans.pb({c,v[i]});
    for(ll i = r;i<si(v);i++) ans.pb({b,v[i]});
    //dbg(si(v));
    return ans;
}

Bob

#include <vector>
#include "Bob.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define fi first
#define sc second
#define here cerr<<"=====================================\n"
#define pb push_back
#define si(a_) (ll)(a_.size())
#define all(a_) a_.begin(),a_.end()
#define ceri(a_,l_,r_) {for(ll i_ = l_;i_<=r_;i_++) cerr<<a_[i_]<< " ";cerr<<endl;}
using namespace std;

using ll = int;
using pll = pair<ll,ll>;

ll n;
const ll maxn = 5005;
ll deg[maxn];
bool tu[maxn];
pll vals[maxn];
vector<ll> g[maxn];
ll cnt[maxn];
long long Bob(std::vector<std::pair<int,int>> V){
    n = 5000;
    for(pll p : V) deg[p.fi]++,deg[p.sc]++,g[p.fi].pb(p.sc),g[p.sc].pb(p.fi);
    vector<ll> w;
    for(ll i = 1;i<=n;i++){
        if(deg[i]>1) w.pb(i);
    }
   // dbg(si(w));
    for(ll x : w) tu[x] = 1;
   // ceri(w,0,si(w)-1);
    for(ll i = 0;i<n;i++){
        if(si(g[i])==0) vals[i] = {-1,-1};
        else{
            vals[i] = {n+1,-1};
            for(ll x : g[i]){
                if(tu[x]) continue;
                vals[i].fi = min(vals[i].fi,x);
                vals[i].sc = max(vals[i].sc,x);
            }
        }
    }
    if(si(w)==1){
        w[0]--;
        return w[0]*5000+w[0]+1;
    }
    for(ll x : w){
       // dbg(x);
       // dbg(vals[x].fi);
        //dbg(vals[x].sc);
    }
    sort(all(w),[](ll i,ll j){
        return vals[i]<vals[j];
    });

    if(si(w)==3){
        w[0]--; w[2]--;
        return 5000*w[0]+w[2]+1;
    }
    if(si(w)==2){
        bool tua = 1;
        for(ll x : g[w[1]]) if(x>=2*n/3) tua = 0;
        ll a = w[0],b = w[1]^w[0];
        if(!tua) swap(a,b);
        a--; b--;
        return a*5000+b+1;
    }

}

Compilation message (stderr)

# 2번째 컴파일 단계

Bob.cpp: In function 'long long int Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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