oj.uz

Submission #142728

# Submission time Handle Problem Language Result Execution time Memory
142728 2019-08-10T15:36:51 Z Ruxandra985 Vrtić (COCI18_vrtic) C++14
48 / 160
 2000 ms 384 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:))


#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;
    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
    for (int i = 1 ; i<=n;i++){
        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;
            sol_curr =max( sol_curr , bag[lt+len] - bag[lt+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 p = 0;
    for (i=1;i<=solv[0];i++){
        nod = v[solv[i]].back();
        v[solv[i]].pop_back();
        while (!f[nod]){
            solf[nod] = bag[++p];
            f[nod] = 1;
            nod = nxt[nod];
        }

    }
    for (i=1;i<=n;i++)
        printf ("%d ",solf[i]);
    return 0;
}

Compilation message

vrtic.cpp: In function 'int main()':
vrtic.cpp:53:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
vrtic.cpp:56:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&nxt[i]);
         ~~~~~~^~~~~~~~~~~~~~
vrtic.cpp:59: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 256 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 384 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB jury has better answer

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB jury has better answer

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 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 2088 ms 380 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 376 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 2081 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 2073 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -