oj.uz

Submission #226537

# Submission time Handle Problem Language Result Execution time Memory
226537 2020-04-24T08:06:27 Z Ruxandra985 Rope (JOI17_rope) C++14
0 / 100
 18 ms 23808 KB 
#include <bits/stdc++.h>
 
using namespace std;
int v[1000010] , fii[1000010] , sol[1000010];
int n , m;
vector <int> w[1000010] , now;
pair <int,int> f[1000010] , fi[1000010];
void solve (int caz){
    int i , first , curr , idx , x , fmax , maxi , j;
 
    for (i = 1 ; i <= m ; i++)
        w[i].clear();
 
    for (i = caz ; i < n ; i += 2 ){
 
        if (v[i] == v[i + 1]){
            w[v[i]].push_back(i); /// unde incepe perechea
        }
        else {
            w[v[i]].push_back(i); /// unde incepe perechea
            w[v[i + 1]].push_back(i); /// unde incepe perechea
        }
 
 
    }
 
    if (i == n)
        w[v[n]].push_back(n);
 
    /// in w, tin pt fiecare culoare, in ce perechi e
 
    for (i = 1 ; i <= m ; i++){
 
        curr = 0;
        first = 2 * w[i].size();
        maxi = 0;
        fmax = 0;
        now.clear();
 
        /// as vrea sa tin cea mai mare val a unui elem modificat
 
        for (j = 0 ; j < w[i].size() ; j++){
 
            idx = w[i][j];
 
            x = v[idx];
            if (f[x].second != i){
                f[x] = make_pair(1 , i);
                now.push_back(x);
            }
            else f[x].first++;
 
 
 
            if (x != i)
                curr++;
 
            x = v[idx + 1];
            if (f[x].second != i){
                f[x] = make_pair(1 , i);
                now.push_back(x);
            }
            else f[x].first++;
 
            if (x != i)
                curr++;
 
        }
 
        /// in now ai valorile schimbate !!!!
 
        if (caz == 2){
            x = v[1];
            if (f[x].second != i){
                f[x] = make_pair(1 , i);
                now.push_back(x);
            }
            else f[x].first++;
 
 
 
            if (x == i)
                first++;
        }
 
        /// in first tii cate elem iau valoarea i
        /// curr = cate elemente ai schimbat in i
 
 
        for (j = 0 ; j < now.size() ; j++){
 
            x = now[j];
 
            if (maxi < fii[x] - f[x].first){
                maxi = fii[x] - f[x].first;
                fmax = x;
            }
 
        }
 
        j = m;
        while (j && f[ fi[j].second ].second == i)
            j--;
 
        if (j){
 
            if (maxi < fi[j].first){
                maxi = fi[j].first;
                fmax = fi[j].second;
            }
        }
 
 
 
 
        sol[i] = min(sol[i] , curr + n - first - maxi);
        sol[fmax] = min(sol[fmax] , curr + n - first - maxi);
 
    }
 
 
 
}
 
 
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i;
    fscanf (fin,"%d%d",&n,&m);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        fi[v[i]].first++;
        fii[v[i]]++;
    }
 
    for (i = 1 ; i <= m ; i++)
        fi[i].second = i;
 
    sort (fi + 1 , fi + m + 1);
 
    if (m == 1){ /// sa scap
        fprintf (fout,"0");
        return 0;
    }
 
    for (i = 1 ; i <= m ; i++)
        sol[i] = 2000000000;
 
    solve (1);
 
    for (i = 1 ; i <= m ; i++){
        f[i].second = 0;
    }
 
 
    solve (2);
 
    for (i = 1 ; i <= m ; i++)
        fprintf (fout,"%d\n",sol[i]);
 
    return 0;
}

Compilation message

rope.cpp: In function 'void solve(int)':
rope.cpp:42:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0 ; j < w[i].size() ; j++){
                      ~~^~~~~~~~~~~~~
rope.cpp:90:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0 ; j < now.size() ; j++){
                      ~~^~~~~~~~~~~~
rope.cpp: In function 'int main()':
rope.cpp:131:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
rope.cpp:133:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Incorrect 17 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Incorrect 17 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Incorrect 17 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Incorrect 17 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Incorrect 17 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -