Submission #1218148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218148		urosk	마술쇼 (APIO24_show)	C++20	5 / 100	2 ms	896 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);
        for(ll i = 1;i<=n;i++){
            if(i^x) ans.pb({i,x});
        }
        return ans;
    x--;
    ll a = x/n;
    ll b = x%n;
    a++;
    b++;
    ll c = (a+b)/2;
    //cerr<<"abc: "<<a<< " "<<b<< " "<<c<<endl;
    if(a==b){
        dbg(si(ans));
        return ans;
    }
    if(c==a||c==b){
        if(min(a,b)>2){
            c = a>b?1:2;
        }else{
            c = a>b?4999:5000;
        }
    }
    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){
        return w[0];
    }
    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,b;
        if(tua){
            a = w[0];
            if(w[1]<w[0]){
                if(w[1]&1) b = a-1;
                else b = a+1;
            }else{

            }
        }
        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:78:1: warning: control reaches end of non-void function [-Wreturn-type]
   78 | }
      | ^

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