Submission #666086

#	Time	Username	Problem	Language	Result	Execution time	Memory
666086		victor_gao	Sirni (COCI17_sirni)	C++17	140 / 140	1944 ms	747944 KiB

sirni

#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
#define C 10000001
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int vis[C+3];
int n,arr[N];
vector<int>vt;
vector<pii>edge[C];
struct dsu{
    int boss[N],sz[N];
    void init(int n){
        for (int i=1;i<=n;i++){
            boss[i]=i; sz[i]=1;
        }
    }
    int find(int x){
        if (boss[x]==x) return x;
        return boss[x]=find(boss[x]);
    }
    void Merge(int a,int b){
        int ra=find(a),rb=find(b);
        if (ra==rb) return;
        if (sz[ra]<sz[rb]) swap(ra,rb);
        sz[ra]+=sz[rb];
        boss[rb]=ra;
    }
}d;
signed main(){
    fast
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
        vt.push_back(arr[i]);
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    int mx=vt.back();
    for (int i=0;i<vt.size();i++)
        vis[vt[i]]=i+1;
    for (int i=mx;i>=1;i--){
        if (vis[i]) continue;
        vis[i]=vis[i+1];
    }
    for (int i=0;i<vt.size();i++){
        int now=vt[i];
        if (i!=(int)(vt.size())-1){
            edge[vt[vis[now+1]-1]%now].push_back({i+1,vis[now+1]});
        }
        for (int j=now;j<=mx;j+=now){
            edge[vt[vis[j]-1]%now].push_back({i+1,vis[j]});
        }
    }
    int ans=0;
    d.init(n);
    for (int i=0;i<mx;i++){
        for (auto j:edge[i]){
            if (d.find(j.x)!=d.find(j.y)){
                ans+=i;
                d.Merge(j.x,j.y);
            }
        }
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

sirni.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
      |                                                                                        ^
sirni.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
sirni.cpp:23:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   23 |     void init(int n){
      |                    ^
sirni.cpp:23:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   28 |     int find(int x){
      |                   ^
sirni.cpp:28:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   32 |     void Merge(int a,int b){
      |                           ^
sirni.cpp:32:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
   40 | signed main(){
      |             ^
sirni.cpp:40:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp: In function 'int main()':
sirni.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i=0;i<vt.size();i++)
      |                  ~^~~~~~~~~~
sirni.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i=0;i<vt.size();i++){
      |                  ~^~~~~~~~~~

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