oj.uz

Submission #142746

# Submission time Handle Problem Language Result Execution time Memory
142746 2019-08-10T16:35:38 Z Ruxandra985 Vrtić (COCI18_vrtic) C++14
80 / 160
 2000 ms 376 KB 
/// este MULT prea neoptim ca sa mearga sincer
/// nici nu stiu exact de ce am zis ca e o idee buna sa bag fix back:))


/// fun fact :) , se pune 1 3 5 7 .... 8 6 4 2

#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#define DIMN 160
using namespace std;
int sol = 1000000000 , sol_curr;
int bag[DIMN],nxt[DIMN],f[DIMN],n,ciclii[DIMN],solf[DIMN];
int curr[DIMN] , solv[DIMN];
int elem;
vector <int> v[DIMN];
void back (int lt){ /// nu cred ca sunt ft multe stari??
    int len,max_curr;
    if (lt==n){ /// solutie
        if (sol > sol_curr){
            sol = sol_curr;
            solv[0] = elem;
            for (int i=1;i<=elem;i++)
                solv[i] = curr[i];
        }
        return;
    }

    /// incerci sa maresti
    max_curr = 0;
    for (int i = 1 ; i<=n;i++){
        if (i>=3)
            max_curr = max (max_curr , bag[lt+i] - bag[lt+i-2]);
        if (ciclii[i]){
            len = i;
            /// urmatorul este un ciclu de lungime len
            /// ai luat deja primele lt elemente
            int before = sol_curr;
            curr[++elem] = i;
            if (len != 1){
                sol_curr = max (sol_curr , max_curr );
                sol_curr = max (sol_curr , bag[lt+2] - bag[lt+1] );
                sol_curr = max (sol_curr , bag[lt + len] - bag[lt + len -1]);
            }
            ciclii[i]--;
            back(lt + len);
            elem--;
            ciclii[i]++;
            sol_curr = before;
        }
    }
}
int main()
{
    //FILE *fin = fopen ("a.in" , "r");
    //FILE *fout = fopen ("a.out" , "w");
    //freopen ("a.in" , "r" , stdin);
    //freopen ("a.out" , "w" , stdout);
    int i,nod,len;
    scanf ("%d",&n);

    for (i=1;i<=n;i++)
        scanf ("%d",&nxt[i]);

    for (i=1;i<=n;i++)
        scanf ("%d",&bag[i]);

    sort (bag + 1, bag + n + 1);

    /// acum trebuie sa vedem cum avem ciclii
    for (i=1;i<=n;i++){
        nod = i;
        if (!f[nod]){
            len = 0;
            while (!f[nod]){
                len ++;
                f[nod] = 1;
                nod = nxt[nod];
            }
            ciclii[len]++;
            v[len].push_back(i);
        }
    }
   /* if (ciclii[n] == 1){ /// un singur ciclu de len n : de testat
        int left = 1 , right = n;
        sol = 0;
        for (i=1;i<=n;i++){
            if (i%2)
                solf[left++] = bag[i];
            else solf[right--] = bag[i];
        }
        for (i=2;i<=n;i++)
            sol = max ( sol , max (solf[i] - solf[i-1] , solf[i-1] - solf[i]));
        printf ("%d\n",sol);
        for (i=1;i<=n;i++)
            printf ("%d ",solf[i]);
        return 0;
    }*/
    /// dinamica are ca parametru un vector de frecventa cu ciclii
    back(0);
    printf ("%d\n",sol);
    memset ( f, 0,sizeof(f));
    int ok;
    int start = 1;
    for (i=1;i<=solv[0];i++){
        nod = v[solv[i]].back();
        v[solv[i]].pop_back();
        int pos = start;
        ok = 0;
        while (!f[nod]){
            if (pos>start + solv[i] - 1){
                ok = 1;
                if (solv[i] % 2)
                    pos = start + (solv[i] - 1) - 1;
                else pos = start + solv[i] - 1;

            }
            solf[nod] = bag[pos];
            f[nod] = 1;
            nod = nxt[nod];
            if (!ok)
                pos+=2;
            else pos-=2;
        }
        start += solv[i];
    }
    for (i=1;i<=n;i++)
        printf ("%d ",solf[i]);
    return 0;
}

Compilation message

vrtic.cpp: In function 'int main()':
vrtic.cpp:62:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
vrtic.cpp:65:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&nxt[i]);
         ~~~~~~^~~~~~~~~~~~~~
vrtic.cpp:68:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&bag[i]);
         ~~~~~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 296 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2023 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -