| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 949576 |
2024-03-19T11:17:42 Z |
ace5 |
Rope (JOI17_rope) |
C++17 |
|
8 ms |
29276 KB |
#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
29276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
29276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
29276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
29276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 2 |
Correct |
8 ms |
29276 KB |
Output is correct |
| 3 |
Correct |
6 ms |
29272 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
29276 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
