Submission #142651

#	Time	Username	Problem	Language	Result	Execution time	Memory
142651		Ruxandra985	Vrtić (COCI18_vrtic)	C++14	16 / 160	2074 ms	396 KiB

vrtic

/// 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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 16 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16