oj.uz

Submission #142651

# Submission time Handle Problem Language Result Execution time Memory
142651 2019-08-10T09:18:58 Z Ruxandra985 Vrtić (COCI18_vrtic) C++14
16 / 160
 2000 ms 396 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");
    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);
        }
    }

    /// 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:52:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d",&n);
     ~~~~~~^~~~~~~~~
vrtic.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&nxt[i]);
         ~~~~~~^~~~~~~~~~~~~~
vrtic.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d",&bag[i]);
         ~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 396 KB jury has better answer

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB jury has better answer

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 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 2025 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 2020 ms 376 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 2074 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 2020 ms 376 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 2036 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -