Submission #1091760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091760		TgX_2	Sirni (COCI17_sirni)	C++17	140 / 140	1146 ms	575140 KiB

sirni

/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

#include <bits/stdc++.h>

#define FOR(i, a, b)       for (int i = (a), _b = (b); i <= _b; i += 1)
#define FORD(i, a, b)      for (int i = (a), _b = (b); i >= _b; i -= 1)
#define FORC(i, a, b, c)   for (int i = (a), _b = (b), _c = (c); i <= _b; i += _c)

#define fi                 first
#define se                 second
#define pb                 push_back
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"

#define ______________TgX______________ main()
// #define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

using   namespace std;
typedef long long          ll;
typedef pair<int, int>     pii;

template<typename T1, typename T2> 
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2> 
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

const int maxn = 1e5 + 7;
const int maxval = 1e7 + 7;

int n, a[maxn], pos[maxval];
vector<pair<int, int>> candidate[maxval];


int par[maxn], child[maxn];
void init() {
    FOR(i, 1, n) {
        par[i] = i;
        child[i] = 1;
    }
}

int find(int u) {
    return (u == par[u] ? u : par[u] = find(par[u]));
}

bool merge(int u, int v) {
    int a = find(u), b = find(v);
    if (a == b) return 1;
    if (child[a] > child[b]) swap(a, b);
    par[b] = a;
    child[a] += child[b];
    return 0;
}

vector<int> va;
void process() {
    cin >> n;
    FOR(i, 1, n) {
        int x; cin >> x;
        va.pb(x);
    }
    sort(all(va));
    va.erase(unique(all(va)), va.end());

    // for(const int &val : va)
    //     cout << val __ ;

    n = 0;
    for(const int &val : va)
        a[++n] = val;
    init();

    FOR(i, 1, n) pos[a[i]] = i;
    FORD(i, a[n], 1) if (pos[i] == 0) pos[i] = pos[i + 1];

    FOR(i, 2, n)
        candidate[a[i] % a[i - 1]].pb({i, i - 1});
    
    FOR(i, 1, n) {
        int cur = a[i] + a[i];
        while(cur <= a[n]) {
            int posi = pos[cur];
            candidate[a[posi] % a[i]].pb({i, posi});
            cur = a[posi] / a[i] * a[i];
            cur += a[i];
        }
    }

    // FOR(i, 0, a[n]) {
    //     cout << i << " : " __ ;
    //     for(const pair<int, int> &val : candidate[i])
    //         cout << val.fi _ val.se __ ;
    //     cout << "---------\n";
    // }


    long long ans = 0;
    FOR(i, 0, a[n]) {
        for(const pair<int, int> &val : candidate[i])
            if (!merge(val.fi, val.se))
                ans += i;
    }

    cout << ans;
}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    if (fopen("temp.inp", "r")) {
        freopen("temp.inp", "r", stdin);
        freopen("temp.out", "w", stdout);
    }
    process();
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message (stderr)

sirni.cpp:21:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | #define ______________TgX______________ main()
      |                                         ^~~~
sirni.cpp:125:1: note: in expansion of macro '______________TgX______________'
  125 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp: In function 'int main()':
sirni.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("temp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("temp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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