Submission #888838

#TimeUsernameProblemLanguageResultExecution timeMemory
888838asdasdqwerSirni (COCI17_sirni)C++14
98 / 140
1784 ms786432 KiB
// #pragma GCC optimze("O3") // #pragma GCC target("avx,avx2,sse4") #include <bits/stdc++.h> using namespace std; #define int int64_t struct DSU { vector<int> p, r; DSU(int n) { p.assign(n,0); r.assign(n,0); for (int i=0;i<n;i++)p[i]=i; } int get(int i) { if (i != p[i]) p[i]=get(p[i]); return p[i]; } bool unite(int a,int b) { assert(a < p.size() && b < p.size()); a=get(a); b=get(b); if (a==b)return false; if (r[a]<r[b])swap(a,b); p[b]=a; if (r[a]==r[b])r[a]++; return true; } }; signed test(int n, vector<int> b) { vector<int> clos(b.back()+1,-1); for (int x:b) { clos[x]=x; } for (int i=clos.size()-2;i>=0;i--) { if (clos[i] == -1) { clos[i]=clos[i+1]; } } typedef array<int,3> pii; vector<pii> edg; for (int x:b) { vector<pii> tmp; if (x != b.back()) { tmp.push_back({clos[x+1] % x, x, clos[x+1]}); } for (int j=2*x;j<=b.back();j+=x) { if (clos[j] != -1) { if (!tmp.size()) { tmp.push_back({clos[j] % x, clos[j], x}); } else if (tmp.back()[1] != clos[j]) { tmp.push_back({clos[j] % x, clos[j], x}); } } } if (tmp.size() == 0 || tmp.back()[1] != clos[b.back()]) { tmp.push_back({clos[b.back()] % x, clos[b.back()], x}); } for (auto y:tmp) edg.push_back(y); } sort(edg.begin(),edg.end()); map<int,int> mp; for (int i=0;i<b.size();i++) { mp[b[i]]=i; } for (auto &x:edg) { // cout<<x[1]<<" "<<x[2]<<"\n"; x[1]=mp[x[1]]; x[2]=mp[x[2]]; } // cout<<"\n"; DSU d(b.size()); int cost=0; for (auto x:edg) { if (d.unite(x[1], x[2])) { // cout<<b[x[1]]<<" "<<b[x[2]]<<"\n"; cost+=x[0]; } } return cost; } // bool brute() { // int len=(rand() % 5)+5; // vector<int> b; // set<int> chose; // for (int i=0;i<len;i++) { // int j=(rand() % 20) + 5; // while (chose.find(j) != chose.end()) { // j=(rand() % 20) + 5; // } // chose.insert(j); // b.push_back(j); // } // sort(b.begin(),b.end()); // typedef array<int,3> pii; // vector<pii> g; // for (int i=0;i<len;i++) { // for (int j=i+1;j<len;j++) { // g.push_back({b[j] % b[i], j, i}); // } // } // sort(g.begin(),g.end()); // DSU d(len); // int cost=0; // for (auto x:g) { // if (d.unite(x[1], x[2])) { // cout<<b[x[1]]<<" "<<b[x[2]]<<"\n"; // cost += x[0]; // } // } // cout<<"\n"; // int cost2 = test(len, b); // cout<<"\n"; // cout<<cost<<" "<<cost2<<"\n\n"; // for (int x:b) { // cout<<x<<" "; // } // cout<<"\n"; // return true; // } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<int> a(n); for (int &x:a)cin>>x; sort(a.begin(),a.end()); vector<int> b; for (int x:a) { if (b.size()==0||b.back()!=x)b.push_back(x); } cout<<test(n,b)<<"\n"; }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sirni.cpp:4:
sirni.cpp: In member function 'bool DSU::unite(int64_t, int64_t)':
sirni.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         assert(a < p.size() && b < p.size());
      |                ~~^~~~~~~~~~
sirni.cpp:23:34: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         assert(a < p.size() && b < p.size());
      |                                ~~^~~~~~~~~~
sirni.cpp: In function 'int test(int64_t, std::vector<long int>)':
sirni.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i=0;i<b.size();i++) {
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...