# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
226514 | Ruxandra985 | Rope (JOI17_rope) | C++14 | 11 ms | 4352 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int v[1000010] , f[1000010] , sol[1000010] , w[1000010];
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , m , i , j , curr , fmax , maxi , first;
fscanf (fin,"%d%d",&n,&m);
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i]);
}
for (i = 1 ; i <= m ; i++)
sol[i] = 2000000000 * (m != 1);
for (i = 1 ; i <= m ; i++){
curr = 0;
maxi = 0;
fmax = 0;
first = 0;
memset (f , 0 , sizeof(f));
/// cazul 1 : mereu 2k = 2k - 1
for (j = 2 ; j <= n ; j += 2){
/// v[j] = v[j - 1]
if (v[j] == i || v[j - 1] == i){ /// astea 2 devin cu i
curr = curr + (v[j] != i) + (v[j - 1] != i);
first += 2;
}
else {
f[v[j]]++;
f[v[j - 1]]++;
if (f[v[j]] > maxi){
maxi = f[v[j]];
fmax = v[j];
}
if (f[v[j - 1]] > maxi){
maxi = f[v[j - 1]];
fmax = v[j - 1];
}
}
}
if (n % 2){ /// ai sarit peste
if (v[n] == i)
first++;
else {
f[v[n]]++;
if (f[v[n]] > maxi){
maxi = f[v[n]];
fmax = v[n];
}
}
}
curr = curr + n - first - f[fmax];
sol[i] = min(sol[i] , curr);
sol[fmax] = min(sol[fmax] , curr);
/// --------------------------------------------------------------------------
curr = 0;
maxi = 0;
fmax = 0;
first = 0;
memset (f , 0 , sizeof(f));
/// cazul 1 : mereu 2k + 1 = 2k
for (j = 2 ; j < n ; j += 2){
/// v[j] = v[j - 1]
if (v[j] == i || v[j + 1] == i){ /// astea 2 devin cu i
curr = curr + (v[j] != i) + (v[j + 1] != i);
first += 2;
}
else {
f[v[j]]++;
f[v[j + 1]]++;
if (f[v[j]] > maxi){
maxi = f[v[j]];
fmax = v[j];
}
if (f[v[j + 1]] > maxi){
maxi = f[v[j + 1]];
fmax = v[j + 1];
}
}
}
if (v[1] == i)
first++;
else {
f[v[1]]++;
if (f[v[1]] > maxi){
maxi = f[v[n]];
fmax = v[n];
}
}
if (n % 2 == 0){ /// ai sarit peste
if (v[n] == i)
first++;
else {
f[v[n]]++;
if (f[v[n]] > maxi){
maxi = f[v[n]];
fmax = v[n];
}
}
}
curr = curr + n - first - f[fmax];
sol[i] = min(sol[i] , curr);
sol[fmax] = min(sol[fmax] , curr);
}
for (i = 1 ; i <= m ; i++)
fprintf (fout,"%d\n",sol[i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |