| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 949565 |
2024-03-19T11:12:31 Z |
ace5 |
Rope (JOI17_rope) |
C++17 |
|
6 ms |
29276 KB |
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(228);
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((*it).second == j)
{
it++;
}
ans[j] = min(ans[j],n-op+(*it).first);
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((*it).second == j)
{
it++;
}
ans[j] = min(ans[j],n-op+(*it).first);
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
rope.cpp: In function 'int main()':
rope.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:56:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:69:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:76:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:97:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int k = 0;k < cc[j].size();++k)
| ~~^~~~~~~~~~~~~~
rope.cpp:106:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | 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 time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 2 |
Correct |
6 ms |
29276 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 2 |
Correct |
6 ms |
29276 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 2 |
Correct |
6 ms |
29276 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 2 |
Correct |
6 ms |
29276 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 2 |
Correct |
6 ms |
29276 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
29276 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
