Submission #830516

#	Time	Username	Problem	Language	Result	Execution time	Memory
830516		Amylopectin	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	793 ms	27212 KiB

Main

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
const int mxn = 4e6 + 10;
struct we
{
    int tt,ii,idx,vall;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.tt < r.tt;
}
bool cmp2(const struct we &l,const struct we &r)
{
    return l.idx < r.idx;
}
struct we sot[mxn] = {};
int ta[mxn] = {},fa[mxn] = {},u[mxn] = {},li[mxn] = {},cma = 0;
int re(int cn,int n,int dep)
{
    int i,j,fn,cl,cr,of;
    if(dep == n)
    {
        for(i=0; i<n; i++)
        {
            ta[i] = li[i];
        }
        for(i=0; i<10000; i++)
        {
            cl = 0;
            cr = n/2;
            for(j=0; j<n; j++)
            {
                if(cl == n/2)
                {
                    fa[j] = ta[cr];
                    cr ++;
                }
                else if(cr == n)
                {
                    fa[j] = ta[cl];
                    cl ++;
                }
                else if(ta[cl] < ta[cr])
                {
                    fa[j] = ta[cl];
                    cl ++;
                }
                else 
                {
                    fa[j] = ta[cr];
                    cr ++;
                }
            }
            of = 0;
            for(j=0; j<n; j++)
            {
                if(ta[j] != fa[j])
                {
                    of = 1;
                }
                ta[j] = fa[j];
            }
            if(of == 0)
            {
                if(i == 7)
                {
                    for(j=0; j<n; j++)
                    {
                        printf("%d ",li[j]);
                    }
                    printf("\n%d\n",i);
                }
                cma = max(cma,i);
                break;
            }
        }
        return 0;
    }
    for(i=1; i<=n; i++)
    {
        if(u[i] == 0)
        {
            u[i] = 1;
            li[dep] = i;
            re(i,n,dep+1);
            u[i] = 0;
        }
    }
    return 0;
}
int main()
{
    // freopen("t2.out","w",stdout);
    int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
    scanf("%d %d",&n,&q);
    for(i=0; i<n; i++)
    {
        scanf("%d",&ta[i]);
    }
    for(i=0; i<q; i++)
    {
        scanf("%d %d",&cn,&cm);
        sot[i] = {cn,cm,i,-1};
    }
    sort(sot,sot+q,cmp);
    // for(j=0; j<n; j++)
    //     {
    //         printf("%d ",ta[j]);
    //     }
    //     printf("\n");
    // re(-1,n,0);
    // printf("%d\n",cma);
    ru = 0;
    while(ru < q && sot[ru].tt == 0)
        {
            sot[ru].vall = ta[sot[ru].ii-1];
            ru ++;
        }
    for(i=1; i<=2000; i++)
    // while(1)
    {
        cl = 0;
        cr = n/2;
        for(j=0; j<n; j++)
        {
            if(cl == n/2)
            {
                fa[j] = ta[cr];
                cr ++;
            }
            else if(cr == n)
            {
                fa[j] = ta[cl];
                cl ++;
            }
            else if(ta[cl] < ta[cr])
            {
                fa[j] = ta[cl];
                cl ++;
            }
            else 
            {
                fa[j] = ta[cr];
                cr ++;
            }
        }
        for(j=0; j<n; j++)
        {
            ta[j] = fa[j];
            
            // printf("%d ",fa[j]);
        }
        while(ru < q && sot[ru].tt == i)
        {
            sot[ru].vall = ta[sot[ru].ii-1];
            ru ++;
        }
        if(ru == q)
        {
            break;
        }
        // printf("\n");
    }
    while(ru < q)
        {
            sot[ru].vall = ta[sot[ru].ii-1];
            ru ++;
        }
    sort(sot,sot+q,cmp2);
    for(i=0; i<q; i++)
    {
        printf("%d\n",sot[i].vall);
    }
}

Compilation message (stderr)

Main.cpp: In function 'int re(int, int, int)':
Main.cpp:23:13: warning: unused variable 'fn' [-Wunused-variable]
   23 |     int i,j,fn,cl,cr,of;
      |             ^~
Main.cpp: In function 'int main()':
Main.cpp:97:17: warning: unused variable 'k' [-Wunused-variable]
   97 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
      |                 ^
Main.cpp:97:19: warning: unused variable 'm' [-Wunused-variable]
   97 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
      |                   ^
Main.cpp:97:27: warning: unused variable 'fn' [-Wunused-variable]
   97 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
      |                           ^~
Main.cpp:97:30: warning: unused variable 'fm' [-Wunused-variable]
   97 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
      |                              ^~
Main.cpp:97:39: warning: unused variable 'cru' [-Wunused-variable]
   97 |     int i,j,n,q,k,m,cn,cm,fn,fm,cl,cr,cru,ru;
      |                                       ^~~
Main.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf("%d",&ta[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25