oj.uz

Submission #830516

# Submission time Handle Problem Language Result Execution time Memory
830516 2023-08-19T07:34:00 Z Amylopectin Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 793 ms 27212 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 19860 KB Output is correct
2 Correct 346 ms 27212 KB Output is correct
3 Correct 357 ms 26284 KB Output is correct
4 Correct 325 ms 25032 KB Output is correct
5 Correct 352 ms 26792 KB Output is correct
6 Correct 329 ms 25376 KB Output is correct
7 Correct 351 ms 26936 KB Output is correct
8 Correct 325 ms 25476 KB Output is correct
9 Correct 335 ms 25300 KB Output is correct
10 Correct 326 ms 25616 KB Output is correct
11 Correct 329 ms 25540 KB Output is correct
12 Correct 323 ms 24440 KB Output is correct
13 Correct 327 ms 25436 KB Output is correct
14 Correct 335 ms 26184 KB Output is correct
15 Correct 330 ms 26024 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 276 ms 24788 KB Output is correct
18 Correct 300 ms 24588 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 1 ms 312 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 793 ms 23960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 272 ms 3168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 19860 KB Output is correct
2 Correct 346 ms 27212 KB Output is correct
3 Correct 357 ms 26284 KB Output is correct
4 Correct 325 ms 25032 KB Output is correct
5 Correct 352 ms 26792 KB Output is correct
6 Correct 329 ms 25376 KB Output is correct
7 Correct 351 ms 26936 KB Output is correct
8 Correct 325 ms 25476 KB Output is correct
9 Correct 335 ms 25300 KB Output is correct
10 Correct 326 ms 25616 KB Output is correct
11 Correct 329 ms 25540 KB Output is correct
12 Correct 323 ms 24440 KB Output is correct
13 Correct 327 ms 25436 KB Output is correct
14 Correct 335 ms 26184 KB Output is correct
15 Correct 330 ms 26024 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 276 ms 24788 KB Output is correct
18 Correct 300 ms 24588 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 1 ms 312 KB Output is correct
21 Incorrect 793 ms 23960 KB Output isn't correct
22 Halted 0 ms 0 KB -