Submission #949576

#TimeUsernameProblemLanguageResultExecution timeMemory
949576ace5Rope (JOI17_rope)C++17
0 / 100
8 ms29276 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1000001; vector<int> cc[maxn]; set<pair<int,int>> ck; int a[maxn]; int u[maxn]; int ans[maxn]; int main() { // ios_base::sync_with_stdio(false); // cin.tie(0); int n,m; cin >> n >> m; for(int j = 0;j < n;++j) { cin >> a[j]; a[j]--; cc[a[j]].push_back(j); } for(int j = 0;j < m;++j) { u[j] = cc[j].size(); ck.insert({-u[j],j}); ans[j] = n+1; } if(m == 1) { cout << 0; return 0; } for(int j = 0;j < m;++j) { int op = u[j]; int xx = 0; for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 1) break; int pr = a[cc[j][k]^1]; ck.erase({-u[pr],pr}); } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 1) break; int pr = a[cc[j][k]^1]; u[pr]--; } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 1) break; int pr = a[cc[j][k]^1]; xx = max(xx,u[pr]); } auto it = ck.begin(); if(ck.size() && (*it).second == j) { it++; } int tk = min(-xx,(ck.size() <= 1 ? 0 : (*it).first)); ans[j] = min(ans[j],n-op+tk); for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 1) break; int pr = a[cc[j][k]^1]; u[pr]++; } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 1) break; int pr = a[cc[j][k]^1]; ck.insert({-u[pr],pr}); } } for(int j = 0;j < m;++j) { int op = u[j]; int xx = 0; for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 0) break; if(cc[j][k] == 0) continue; int pr = a[((cc[j][k]-1)^1)+1]; ck.erase({-u[pr],pr}); } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 0) break; if(cc[j][k] == 0) continue; int pr = a[((cc[j][k]-1)^1)+1]; u[pr]--; } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 0) break; if(cc[j][k] == 0) continue; int pr = a[((cc[j][k]-1)^1)+1]; xx = max(xx,u[pr]); } auto it = ck.begin(); if(ck.size() && (*it).second == j) { it++; } int tk = min(-xx,(ck.size() <= 1 ? 0 : (*it).first)); ans[j] = min(ans[j],n-op+tk); for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 0) break; if(cc[j][k] == 0) continue; int pr = a[((cc[j][k]-1)^1)+1]; u[pr]++; } for(int k = 0;k < cc[j].size();++k) { if(cc[j][k] == n-1 && n%2 == 0) break; if(cc[j][k] == 0) continue; int pr = a[((cc[j][k]-1)^1)+1]; ck.insert({-u[pr],pr}); } cout << ans[j] << "\n"; } }

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:47:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:68:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:96:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:105:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:121:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
rope.cpp:130:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for(int k = 0;k < cc[j].size();++k)
      |                       ~~^~~~~~~~~~~~~~
#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...