Submission #1057626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057626		vjudge1	Sirni (COCI17_sirni)	C++17	140 / 140	672 ms	622096 KiB

sirni

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const int amax = 1e7;
int n, a[nmax], mx = 0;
vector <bool> vs;
vector <int> nxt, pos;
vector <vector <pii>> adj;
struct disjoint
{
    int root[nmax], sz[nmax];
    void init(int _sz)
    {
        iota(root + 1, root + _sz + 1, 1);
        memset(sz, 1, (_sz + 1) * sizeof(int));
    }
    int findset(int u)
    {
        if (root[u] == u) return u;
        return root[u] = findset(root[u]);
    }
    bool merge(int u, int v)
    {
        if ((u = findset(u)) == (v = findset(v))) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        root[v] = u;
        return 1;
    }
} dsu;
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    vs.resize(mx + 1);
    adj.resize(mx + 1);
    nxt.resize(mx + 2);
    pos.resize(mx + 2);
    dsu.init(n);
    for (int i = 1; i <= n; ++i)
    {
        nxt[a[i]] = a[i];
        if (!pos[a[i]]) pos[a[i]] = i;
    }
    for (int i = mx - 1; i >= 1; --i)
        if (!nxt[i])
            nxt[i] = nxt[i + 1];
    for (int i = 1; i <= n; ++i)
    {
        if (vs[a[i]]) continue;
        vs[a[i]] = 1;
        if (nxt[a[i] + 1])
            if ((a[i] << 1) > mx || nxt[a[i] << 1] != nxt[a[i] + 1])
                adj[nxt[a[i] + 1] - a[i]].eb(i, pos[nxt[a[i] + 1]]);
        for (int j = (a[i] << 1); j <= mx && nxt[j]; j += a[i])
            if (j + a[i] > mx || nxt[j + a[i]] != nxt[j])
                adj[nxt[j] - j].eb(i, pos[nxt[j]]);
    }
    ll ans = 0;
    for (int weight = 0; weight < mx; ++weight)
        for (auto &[u, v] : adj[weight])
            if (dsu.merge(u, v)) ans += weight;
    cout << ans;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:9:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:45:31: note: in expansion of macro 'nx'
   45 |     if (ifstream(task".inp")) nx
      |                               ^~
sirni.cpp:9:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:45:31: note: in expansion of macro 'nx'
   45 |     if (ifstream(task".inp")) nx
      |                               ^~

• 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