Submission #1153513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153513		kitkat12	Sirni (COCI17_sirni)	C++20	70 / 140	2671 ms	851968 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name)) 
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 1e5+3;
vector<int> P;
int p[nmax],sz[nmax];
int get(int a){
    return p[a]=(p[a]==a?a:get(p[a]));
}
void uni(int a, int b){
    a=get(a);
    b=get(b);
    if(a==b)return;
    if(sz[a]<sz[b])swap(a,b);
    p[b]=a;
    sz[a]+=sz[b];
}
int foo(int a, int b){
    return min(a%b, b%a);
}
struct Compare{
    bool comp(pii a,pii b){
        return foo(P[a.S],P[a.F]) < foo(P[b.S],P[b.F]);
    }
};
int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    li(i,0,nmax){p[i]=i;sz[i]=1;}
    int n,a;
    cin>>n;
    li(i,0,n){
        cin>>a;P.pb(a);
        if(a==0){
            cout<<0;
            return 0;
        }
    }
    sort(all(P));	

    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;

    li(i,0,n){
        for(int j=P[i]; j<=P[n-1]; j+=P[i]){
            auto it = lower_bound(all(P),j);
            if(it==P.end()){
                pq.push({foo(P[i],P[n-1]),{i,n-1}});
                break;
            }  
            int idx = it-P.begin();
            pq.push({foo(P[i],P[idx]),{i,idx}});
            pq.push({foo(P[i],P[max(0,idx-1)]),{i,max(0,idx-1)}});
            pq.push({foo(P[i],P[min(idx+1,n-1)]),{i,min(idx+1,n-1)}});
        }
    }

    int cnt =0;
    ll res = 0;
    while(!pq.empty() && cnt<n-1){
        auto [i,j] = pq.top().S;
        pq.pop();
        if(get(i)==get(j)) continue;

        uni(i,j);
        res+=foo(P[j],P[i]);
        cnt++;

        pq.push({foo(P[i],P[max(0,j-1)]),{i,max(0,j-1)}});
        pq.push({foo(P[i],P[min(j+1,n-1)]),{i,min(j+1,n-1)}});
    }

    cout<<res;

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14