oj.uz

Submission #225812

# Submission time Handle Problem Language Result Execution time Memory
225812 2020-04-21T18:08:01 Z CaroLinda Building Skyscrapers (CEOI19_skyscrapers) C++14
100 / 100
 3474 ms 192156 KB 
#include <bits/stdc++.h>

static struct FASTIO {

  char READ_CHARACTER; bool REMAINING_CHARACTER = false;

  inline void ignore(); inline void flush();

  template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
  /*                                                          Fast I/O Code Optimizer                                                          */
  template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
  /*                    A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables                   */
  template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
  /*                                                    Use it on fastio.pythonanywhere.com                                                    */
  template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
  /*                                          Github Project: github.com/bfs07/Fast-IO-Code-Optimizer                                          */
  template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
  inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x); 
  inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
  inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
  inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
  inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
  inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
  inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
  inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
  inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
  inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x); 
  inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
  template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);

} __FIO__;


#include <bits/stdc++.h>

#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAX = 850100 ;
const int MAXN = 150100 ;
const int inf = 1e9+10 ;

using namespace std ;

int N , T , idx ;
int X[MAX] , Y[MAX] , pai[MAX] , pai_aux[MAXN] ;
int dx[8] = { 1,-1,0,0, 1,-1,1,-1 } , dy[8] = { 0,0,1,-1, -1,1, 1, -1} ;
int dx_cyclic[8] = { -1 , -1 , 0 , 1 , 1 ,1 , 0, -1 } , dy_cyclic[8] = { 0 , -1 , -1 , -1, 0 , 1 , 1 ,1  } ;
pii id[MAX] ;
bool is_full[MAX] , reachable[MAX] , checked[MAX] , freq[MAX] ;
map< pii , int > mp ;
set<int> s ;
vector<int> ans , fila , fila2 ;
vector<int> componente[MAX] , adj[MAX] , adj_cyclic[MAX] ;
set<int>::iterator it ;

 

int get_code(int x, int y)
{

    if( mp.find( mk(x,y) ) == mp.end() ) return 0 ;
    return mp.find( mk(x,y) )->ss ;

}

int find(int x)
{
    if( x == pai[x] ) return x ;
    return pai[x] = find( pai[x] ) ;
}


bool identify_articulation(int name)
{
    int j = -1 ;

    lp(i,0,8)
        if( is_full[ adj_cyclic[name][i] ] ) { j = i ; break ; }

    if( j == -1 ) return false ;

    int beg = -1, en = beg , times = 0 ;
    bool resp = false;

    for(int i = (j+1)%8 ; true ; i = (i+1)%8 )
    {

        if( i == ((j+1)%8) && times == 1 ) break ;
        else if( i == ((j+1)%8) && times == 0 ) times ++ ;

        int c = adj_cyclic[name][i] ;

        if( is_full[c] )
        {

            if( beg == -1 ) continue ;
            if( beg % 2 == 1 && en == beg )  { beg = -1 ; continue ; }

            if( freq[ find( adj_cyclic[name][beg]) ] ) resp = true ;
            else freq[ find( adj_cyclic[name][beg]) ] = true ;

            beg = -1 ;
            continue ;
        }

        if( beg == -1 ) beg = en = i ;
        else en = i ;

    }

    lp(i,0,8)
        freq[ find( adj_cyclic[name][i]) ] = false ;

    return resp ;

}

bool identify_infinity(int name)
{
    lp(i,0,4)
    {
        int c = adj[name][i] ;
        if(c != 0 && reachable[ find(c) ]) return true ;
    }

    return false ;

}
bool check(int i) { return ( !identify_articulation(i) )&identify_infinity(i) ; }

inline void to_change(int name)
{

    for(int i = 0 ; i < 8 ; i++ )
    {

        int c = adj[name][i] ;

        if( c == 0 || !is_full[c] ) continue ;

        if( !freq[c] )
        {
            freq[c] = true ;
            fila2.pb(c) ;
        }

    }

}

bool join(int a, int b, bool ok )
{

    a = find(a) ;
    b = find(b) ;

    if(a==b) return false ;

    if( componente[a].size() > componente[b].size() ) swap( a , b  );

    pai[a] = b ;
    if( !reachable[b] && reachable[a] )
    {

        reachable[b] = true ;
        if(ok) for(int i : componente[b] ) fila.pb(i) ;
    }

    for( int i : componente[a] )
    {
        componente[b].pb(i) ;
        if( ok ) fila.pb(i) ;
    }
    componente[a].clear() ;


    return true ;

}

int find_aux(int x)
{
    if( x == pai_aux[x] ) return x ;
    return pai_aux[x] = find_aux( pai_aux[x] ) ;
}
inline void join_aux(int a, int b)
{
    a = find_aux(a) ;
    b = find_aux(b) ;

    if( rand() % 2 ) swap(a,b) ;

    pai_aux[a] = b ;

}

int main()
{
    scanf("%d%d", &N , &T ) ;
    lp(i,1,N+1)
    {
        scanf("%d%d", &X[i] , &Y[i]) ;
        mp.insert( mk( mk( X[i] , Y[i] ) , i ) ) ;
        is_full[i] = true ;
        pai_aux[i] = i ;
    }

    idx = N ;

    lp(i,1,N+1)
    {
        for(int j = 0 ; j < 8 ; j++ )
        {

            int nx = dx[j] + X[i] ;
            int ny = dy[j] + Y[i] ;

            if( mp.find( mk(nx,ny) ) == mp.end() ) mp.insert( mk( mk(nx,ny) , ++idx ) ) ;

            if( is_full[ get_code(nx,ny) ] ) join_aux( i , get_code(nx,ny) ) ;

        }
    }

    lp(i,2,N+1)
        if( find_aux(i) != find_aux(1) ) {  printf("NO\n") ; return 0 ; }

    for(auto p : mp )
    {
        X[p.ss] = p.ff.ff ;
        Y[p.ss] = p.ff.ss ;
        pai[ p.ss ] = p.ss ;
        componente[p.ss].pb( p.ss ) ;

        for(int j = 0 , nx , ny , c ; j < 8 ; j++ )
        {

            nx = p.ff.ff + dx[j] ;
            ny = p.ff.ss + dy[j] ;
            c = get_code(nx,ny) ;

            adj[p.ss].pb(c) ;

            nx = p.ff.ff + dx_cyclic[j] ;
            ny = p.ff.ss + dy_cyclic[j] ;
            c = get_code(nx,ny) ;

            adj_cyclic[p.ss].pb( c ) ;

        }

    }

    int id = -1 , mn = inf ;

    for(auto p : mp )
        if( p.ff.ff < mn ) mn = p.ff.ff , id = p.ss ;
    reachable[id] = true ;

    for(auto p : mp )
    {

        if( is_full[p.ss] ) continue ;

        lp(i,0,4)
            if( adj[p.ss][i] != 0 && !is_full[ adj[p.ss][i] ] )
                join( p.ss , adj[p.ss][i] , false ) ;

    }


    lp(i,1,N+1)
        if( check(i) )
        {
            s.insert(i) ;
            checked[i] = true ;
        }

    while( s.size() > 0 )
    {
        it = prev( s.end() ) ;

        int best_id = *it ;
        s.erase(it) ;

        ans.pb( best_id ) ;
        is_full[best_id] = false ;
        fila.pb(best_id) ;

        lp(i,0,4)
            if( !is_full[ adj[best_id][i] ] )
                join( adj[best_id][i] , best_id , true ) ;

        for(int i : fila ) to_change(i) ;
        fila.clear() ;

        for(int i : fila2 )
        {
            freq[i] = false ;

            bool val = check(i) ;

            if( val && !checked[i] )
            {
                s.insert(i) ;
                checked[i] = true ;
            }
            else if( !val && checked[i] )
            {
                s.erase( s.find(i) ) ;
                checked[i] = false ;
            }

        }

        fila2.clear() ;

    }

    printf("YES\n") ;
    reverse(all(ans)) ;
    for(int i : ans ) printf("%d\n" , i ) ;

}


#undef all
#undef lp
#undef debug
#undef all
#undef lp
#undef ss
#undef ff
#undef ll
#undef pb
#undef pii
#undef mk

inline void FASTIO::ignore() {
  if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}

inline void FASTIO::flush() {
  fflush(stdout);
}

// cin modifications

template <typename T>
inline bool FASTIO::READ_INT(T &x) {
  x = 0; T sig = 1;
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
  x *= sig; REMAINING_CHARACTER = true;
  return true;
}

template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_GETLINE(std::string &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = false;
  return true;
}

template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  x = READ_CHARACTER; REMAINING_CHARACTER = false;
  return true;
}


template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  char *ptr = &x[0];
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
  *ptr = '\0', REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
  std::string y;
  if(READ_STRING(y) == false)
    return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}

template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
  return (scanf("%f", &x) != EOF);
}

template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
  double y;
  if(scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}

template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  int i = 0; REMAINING_CHARACTER = true;
  while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
  return true;
}

inline bool FASTIO::READ_VAR(short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(std::string &x) {
  return READ_STRING(x);    
}

inline bool FASTIO::READ_VAR(char &x) {
  return READ_CHAR(x);
}

template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(char*& x) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(float &x) {
  return READ_FLOAT(x);
}

inline bool FASTIO::READ_VAR(double &x) {
  return READ_DOUBLE(x);
}

inline bool FASTIO::READ_VAR(long double &x) {
  return READ_DOUBLE(x);
}

template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
  return READ_BITSET(x);
}

// cout modifications

template <typename T>
inline void FASTIO::WRITE_INT(T x) {
  if (x < 0) {putchar('-'); x = -x; }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  }
  while (x);
  do  { putchar(*--writePtr); }
  while (writePtr > writeBuffer);
}

inline void FASTIO::WRITE_CHAR(char x) {
  putchar(x);
}

inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
  while(*x != '\0')
    putchar(*x++);
}

inline void FASTIO::WRITE_STRING(std::string &x) {
  for(char c: x) 
    putchar(c);
}

inline void FASTIO::WRITE_FLOAT(float x) {
  printf("%f", x);
}

template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
  printf("%lf", (double)x);
}

template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
  for(int i = (int)x.size() - 1; i >= 0; i--)
    putchar(x[i] + 48);
}

inline void FASTIO::WRITE_VAR(bool x) {
  WRITE_INT(x);
}

inline void FASTIO::WRITE_VAR(short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(std::string &x) {
  WRITE_STRING(x);    
}

inline void FASTIO::WRITE_VAR(char x) {
  WRITE_CHAR(x);
}

inline void FASTIO::WRITE_VAR(const char *x) {
  WRITE_CHAR_ARRAY(x);
}

inline void FASTIO::WRITE_VAR(float x) {
  WRITE_FLOAT(x);
}

inline void FASTIO::WRITE_VAR(double x) {
  WRITE_DOUBLE(x);
}

inline void FASTIO::WRITE_VAR(long double x) {
  WRITE_DOUBLE(x);
}

template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
  WRITE_BITSET(x);
}

Compilation message

skyscrapers.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
skyscrapers.cpp:552:14:   required from here
skyscrapers.cpp:511:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
   if (x < 0) {putchar('-'); x = -x; }
       ~~^~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:207:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N , &T ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~
skyscrapers.cpp:210:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &X[i] , &Y[i]) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60280 KB ans=YES N=1
2 Correct 39 ms 60280 KB ans=YES N=4
3 Correct 39 ms 60288 KB ans=NO N=4
4 Correct 40 ms 60288 KB ans=YES N=5
5 Correct 38 ms 60288 KB ans=YES N=9
6 Correct 39 ms 60288 KB ans=YES N=5
7 Correct 38 ms 60288 KB ans=NO N=9
8 Correct 38 ms 60280 KB ans=NO N=10
9 Correct 39 ms 60288 KB ans=YES N=10
10 Correct 38 ms 60280 KB ans=YES N=10
11 Correct 38 ms 60280 KB ans=YES N=10
12 Correct 39 ms 60284 KB ans=YES N=9
13 Correct 38 ms 60280 KB ans=YES N=9
14 Correct 38 ms 60288 KB ans=YES N=8
15 Correct 39 ms 60288 KB ans=YES N=8
16 Correct 38 ms 60288 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60280 KB ans=YES N=1
2 Correct 39 ms 60280 KB ans=YES N=4
3 Correct 39 ms 60288 KB ans=NO N=4
4 Correct 40 ms 60288 KB ans=YES N=5
5 Correct 38 ms 60288 KB ans=YES N=9
6 Correct 39 ms 60288 KB ans=YES N=5
7 Correct 38 ms 60288 KB ans=NO N=9
8 Correct 38 ms 60280 KB ans=NO N=10
9 Correct 39 ms 60288 KB ans=YES N=10
10 Correct 38 ms 60280 KB ans=YES N=10
11 Correct 38 ms 60280 KB ans=YES N=10
12 Correct 39 ms 60284 KB ans=YES N=9
13 Correct 38 ms 60280 KB ans=YES N=9
14 Correct 38 ms 60288 KB ans=YES N=8
15 Correct 39 ms 60288 KB ans=YES N=8
16 Correct 38 ms 60288 KB ans=NO N=2
17 Correct 37 ms 60280 KB ans=YES N=17
18 Correct 39 ms 60280 KB ans=YES N=25
19 Correct 39 ms 60280 KB ans=YES N=100
20 Correct 41 ms 60280 KB ans=YES N=185
21 Correct 39 ms 60280 KB ans=NO N=174
22 Correct 40 ms 60280 KB ans=YES N=90
23 Correct 39 ms 60256 KB ans=YES N=63
24 Correct 45 ms 60288 KB ans=YES N=87
25 Correct 41 ms 60280 KB ans=YES N=183
26 Correct 40 ms 60280 KB ans=YES N=188
27 Correct 41 ms 60280 KB ans=YES N=183
28 Correct 39 ms 60288 KB ans=YES N=189
29 Correct 40 ms 60288 KB ans=YES N=200
30 Correct 40 ms 60416 KB ans=YES N=190
31 Correct 40 ms 60288 KB ans=YES N=187
32 Correct 40 ms 60412 KB ans=YES N=187
33 Correct 40 ms 60412 KB ans=YES N=182
34 Correct 41 ms 60416 KB ans=YES N=184
35 Correct 40 ms 60416 KB ans=YES N=188
36 Correct 41 ms 60408 KB ans=YES N=181
37 Correct 41 ms 60408 KB ans=YES N=188
38 Correct 44 ms 60460 KB ans=YES N=191
39 Correct 43 ms 60416 KB ans=YES N=196
40 Correct 41 ms 60408 KB ans=YES N=196
41 Correct 41 ms 60408 KB ans=YES N=196
42 Correct 40 ms 60416 KB ans=YES N=196
43 Correct 41 ms 60416 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60280 KB ans=YES N=1
2 Correct 39 ms 60280 KB ans=YES N=4
3 Correct 39 ms 60288 KB ans=NO N=4
4 Correct 40 ms 60288 KB ans=YES N=5
5 Correct 38 ms 60288 KB ans=YES N=9
6 Correct 39 ms 60288 KB ans=YES N=5
7 Correct 38 ms 60288 KB ans=NO N=9
8 Correct 38 ms 60280 KB ans=NO N=10
9 Correct 39 ms 60288 KB ans=YES N=10
10 Correct 38 ms 60280 KB ans=YES N=10
11 Correct 38 ms 60280 KB ans=YES N=10
12 Correct 39 ms 60284 KB ans=YES N=9
13 Correct 38 ms 60280 KB ans=YES N=9
14 Correct 38 ms 60288 KB ans=YES N=8
15 Correct 39 ms 60288 KB ans=YES N=8
16 Correct 38 ms 60288 KB ans=NO N=2
17 Correct 37 ms 60280 KB ans=YES N=17
18 Correct 39 ms 60280 KB ans=YES N=25
19 Correct 39 ms 60280 KB ans=YES N=100
20 Correct 41 ms 60280 KB ans=YES N=185
21 Correct 39 ms 60280 KB ans=NO N=174
22 Correct 40 ms 60280 KB ans=YES N=90
23 Correct 39 ms 60256 KB ans=YES N=63
24 Correct 45 ms 60288 KB ans=YES N=87
25 Correct 41 ms 60280 KB ans=YES N=183
26 Correct 40 ms 60280 KB ans=YES N=188
27 Correct 41 ms 60280 KB ans=YES N=183
28 Correct 39 ms 60288 KB ans=YES N=189
29 Correct 40 ms 60288 KB ans=YES N=200
30 Correct 40 ms 60416 KB ans=YES N=190
31 Correct 40 ms 60288 KB ans=YES N=187
32 Correct 40 ms 60412 KB ans=YES N=187
33 Correct 40 ms 60412 KB ans=YES N=182
34 Correct 41 ms 60416 KB ans=YES N=184
35 Correct 40 ms 60416 KB ans=YES N=188
36 Correct 41 ms 60408 KB ans=YES N=181
37 Correct 41 ms 60408 KB ans=YES N=188
38 Correct 44 ms 60460 KB ans=YES N=191
39 Correct 43 ms 60416 KB ans=YES N=196
40 Correct 41 ms 60408 KB ans=YES N=196
41 Correct 41 ms 60408 KB ans=YES N=196
42 Correct 40 ms 60416 KB ans=YES N=196
43 Correct 41 ms 60416 KB ans=YES N=195
44 Correct 47 ms 61304 KB ans=NO N=1934
45 Correct 45 ms 60664 KB ans=NO N=1965
46 Correct 51 ms 60800 KB ans=YES N=1824
47 Correct 53 ms 60800 KB ans=YES N=1981
48 Correct 54 ms 60792 KB ans=YES N=1814
49 Correct 53 ms 60920 KB ans=YES N=1854
50 Correct 53 ms 60792 KB ans=YES N=1831
51 Correct 54 ms 60792 KB ans=YES N=2000
52 Correct 56 ms 61048 KB ans=YES N=1847
53 Correct 57 ms 61176 KB ans=YES N=1819
54 Correct 54 ms 60792 KB ans=YES N=1986
55 Correct 62 ms 61432 KB ans=YES N=2000
56 Correct 62 ms 61688 KB ans=YES N=1834
57 Correct 62 ms 61560 KB ans=YES N=1860
58 Correct 62 ms 61688 KB ans=YES N=1898
59 Correct 59 ms 61436 KB ans=YES N=1832
60 Correct 66 ms 61944 KB ans=YES N=1929
61 Correct 55 ms 61048 KB ans=YES N=1919
62 Correct 61 ms 61432 KB ans=YES N=1882
63 Correct 68 ms 61944 KB ans=YES N=1922
64 Correct 56 ms 61048 KB ans=YES N=1989
65 Correct 59 ms 61304 KB ans=YES N=1978
66 Correct 60 ms 61308 KB ans=YES N=1867
67 Correct 60 ms 61432 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 61304 KB ans=NO N=1934
2 Correct 44 ms 60672 KB ans=NO N=1965
3 Correct 52 ms 60792 KB ans=YES N=1824
4 Correct 53 ms 60792 KB ans=YES N=1981
5 Correct 51 ms 60792 KB ans=YES N=1814
6 Correct 53 ms 60928 KB ans=YES N=1854
7 Correct 53 ms 60792 KB ans=YES N=1831
8 Correct 53 ms 60920 KB ans=YES N=2000
9 Correct 56 ms 61048 KB ans=YES N=1847
10 Correct 58 ms 61176 KB ans=YES N=1819
11 Correct 54 ms 60792 KB ans=YES N=1986
12 Correct 61 ms 61432 KB ans=YES N=2000
13 Correct 64 ms 61688 KB ans=YES N=1834
14 Correct 61 ms 61560 KB ans=YES N=1860
15 Correct 63 ms 61688 KB ans=YES N=1898
16 Correct 60 ms 61432 KB ans=YES N=1832
17 Correct 67 ms 61944 KB ans=YES N=1929
18 Correct 55 ms 61048 KB ans=YES N=1919
19 Correct 61 ms 61560 KB ans=YES N=1882
20 Correct 67 ms 61944 KB ans=YES N=1922
21 Correct 54 ms 61048 KB ans=YES N=1989
22 Correct 58 ms 61304 KB ans=YES N=1978
23 Correct 57 ms 61304 KB ans=YES N=1867

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 60280 KB ans=YES N=1
2 Correct 39 ms 60280 KB ans=YES N=4
3 Correct 39 ms 60288 KB ans=NO N=4
4 Correct 40 ms 60288 KB ans=YES N=5
5 Correct 38 ms 60288 KB ans=YES N=9
6 Correct 39 ms 60288 KB ans=YES N=5
7 Correct 38 ms 60288 KB ans=NO N=9
8 Correct 38 ms 60280 KB ans=NO N=10
9 Correct 39 ms 60288 KB ans=YES N=10
10 Correct 38 ms 60280 KB ans=YES N=10
11 Correct 38 ms 60280 KB ans=YES N=10
12 Correct 39 ms 60284 KB ans=YES N=9
13 Correct 38 ms 60280 KB ans=YES N=9
14 Correct 38 ms 60288 KB ans=YES N=8
15 Correct 39 ms 60288 KB ans=YES N=8
16 Correct 38 ms 60288 KB ans=NO N=2
17 Correct 37 ms 60280 KB ans=YES N=17
18 Correct 39 ms 60280 KB ans=YES N=25
19 Correct 39 ms 60280 KB ans=YES N=100
20 Correct 41 ms 60280 KB ans=YES N=185
21 Correct 39 ms 60280 KB ans=NO N=174
22 Correct 40 ms 60280 KB ans=YES N=90
23 Correct 39 ms 60256 KB ans=YES N=63
24 Correct 45 ms 60288 KB ans=YES N=87
25 Correct 41 ms 60280 KB ans=YES N=183
26 Correct 40 ms 60280 KB ans=YES N=188
27 Correct 41 ms 60280 KB ans=YES N=183
28 Correct 39 ms 60288 KB ans=YES N=189
29 Correct 40 ms 60288 KB ans=YES N=200
30 Correct 40 ms 60416 KB ans=YES N=190
31 Correct 40 ms 60288 KB ans=YES N=187
32 Correct 40 ms 60412 KB ans=YES N=187
33 Correct 40 ms 60412 KB ans=YES N=182
34 Correct 41 ms 60416 KB ans=YES N=184
35 Correct 40 ms 60416 KB ans=YES N=188
36 Correct 41 ms 60408 KB ans=YES N=181
37 Correct 41 ms 60408 KB ans=YES N=188
38 Correct 44 ms 60460 KB ans=YES N=191
39 Correct 43 ms 60416 KB ans=YES N=196
40 Correct 41 ms 60408 KB ans=YES N=196
41 Correct 41 ms 60408 KB ans=YES N=196
42 Correct 40 ms 60416 KB ans=YES N=196
43 Correct 41 ms 60416 KB ans=YES N=195
44 Correct 47 ms 61304 KB ans=NO N=1934
45 Correct 45 ms 60664 KB ans=NO N=1965
46 Correct 51 ms 60800 KB ans=YES N=1824
47 Correct 53 ms 60800 KB ans=YES N=1981
48 Correct 54 ms 60792 KB ans=YES N=1814
49 Correct 53 ms 60920 KB ans=YES N=1854
50 Correct 53 ms 60792 KB ans=YES N=1831
51 Correct 54 ms 60792 KB ans=YES N=2000
52 Correct 56 ms 61048 KB ans=YES N=1847
53 Correct 57 ms 61176 KB ans=YES N=1819
54 Correct 54 ms 60792 KB ans=YES N=1986
55 Correct 62 ms 61432 KB ans=YES N=2000
56 Correct 62 ms 61688 KB ans=YES N=1834
57 Correct 62 ms 61560 KB ans=YES N=1860
58 Correct 62 ms 61688 KB ans=YES N=1898
59 Correct 59 ms 61436 KB ans=YES N=1832
60 Correct 66 ms 61944 KB ans=YES N=1929
61 Correct 55 ms 61048 KB ans=YES N=1919
62 Correct 61 ms 61432 KB ans=YES N=1882
63 Correct 68 ms 61944 KB ans=YES N=1922
64 Correct 56 ms 61048 KB ans=YES N=1989
65 Correct 59 ms 61304 KB ans=YES N=1978
66 Correct 60 ms 61308 KB ans=YES N=1867
67 Correct 60 ms 61432 KB ans=YES N=1942
68 Correct 378 ms 67704 KB ans=NO N=66151
69 Correct 477 ms 89376 KB ans=NO N=64333
70 Correct 740 ms 76648 KB ans=YES N=69316
71 Correct 705 ms 76408 KB ans=YES N=66695
72 Correct 751 ms 76792 KB ans=YES N=68436
73 Correct 762 ms 77164 KB ans=YES N=70000
74 Correct 750 ms 77284 KB ans=YES N=68501
75 Correct 795 ms 78172 KB ans=YES N=70000
76 Correct 792 ms 79852 KB ans=YES N=65009
77 Correct 1174 ms 95464 KB ans=YES N=67007
78 Correct 1284 ms 102828 KB ans=YES N=66357
79 Correct 1329 ms 107888 KB ans=YES N=65430
80 Correct 1320 ms 105704 KB ans=YES N=65790
81 Correct 1273 ms 102388 KB ans=YES N=66020
82 Correct 1276 ms 98220 KB ans=YES N=65809
83 Correct 938 ms 83960 KB ans=YES N=65651
84 Correct 1649 ms 120324 KB ans=YES N=68040
85 Correct 1449 ms 112748 KB ans=YES N=66570
86 Correct 779 ms 78364 KB ans=YES N=65421
87 Correct 829 ms 81004 KB ans=YES N=68351
88 Correct 696 ms 76008 KB ans=YES N=67027
89 Correct 916 ms 90476 KB ans=YES N=68879
90 Correct 826 ms 81256 KB ans=YES N=67256
91 Correct 1899 ms 97564 KB ans=YES N=148315
92 Correct 1155 ms 131936 KB ans=NO N=142745
93 Correct 1002 ms 145912 KB ans=NO N=148443
94 Correct 1818 ms 95564 KB ans=YES N=148328
95 Correct 1806 ms 95452 KB ans=YES N=147855
96 Correct 1845 ms 95708 KB ans=YES N=150000
97 Correct 1844 ms 94692 KB ans=YES N=144725
98 Correct 1825 ms 95596 KB ans=YES N=149445
99 Correct 1815 ms 94936 KB ans=YES N=144455
100 Correct 1792 ms 94556 KB ans=YES N=143487
101 Correct 1885 ms 96300 KB ans=YES N=149688
102 Correct 2830 ms 138396 KB ans=YES N=141481
103 Correct 3428 ms 177000 KB ans=YES N=147430
104 Correct 2330 ms 119064 KB ans=YES N=142247
105 Correct 2863 ms 133224 KB ans=YES N=149941
106 Correct 3158 ms 168928 KB ans=YES N=141635
107 Correct 3216 ms 158784 KB ans=YES N=142896
108 Correct 3428 ms 173272 KB ans=YES N=142069
109 Correct 2099 ms 107028 KB ans=YES N=142378
110 Correct 2727 ms 147236 KB ans=YES N=150000
111 Correct 3460 ms 192004 KB ans=YES N=141452
112 Correct 3169 ms 184084 KB ans=YES N=134453
113 Correct 3018 ms 185788 KB ans=YES N=144172

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 67704 KB ans=NO N=66151
2 Correct 475 ms 89336 KB ans=NO N=64333
3 Correct 736 ms 76740 KB ans=YES N=69316
4 Correct 693 ms 76136 KB ans=YES N=66695
5 Correct 732 ms 76644 KB ans=YES N=68436
6 Correct 753 ms 77160 KB ans=YES N=70000
7 Correct 738 ms 77160 KB ans=YES N=68501
8 Correct 794 ms 78184 KB ans=YES N=70000
9 Correct 793 ms 79772 KB ans=YES N=65009
10 Correct 1176 ms 95440 KB ans=YES N=67007
11 Correct 1255 ms 102740 KB ans=YES N=66357
12 Correct 1368 ms 107692 KB ans=YES N=65430
13 Correct 1359 ms 105676 KB ans=YES N=65790
14 Correct 1282 ms 102384 KB ans=YES N=66020
15 Correct 1258 ms 98280 KB ans=YES N=65809
16 Correct 939 ms 84136 KB ans=YES N=65651
17 Correct 1665 ms 120300 KB ans=YES N=68040
18 Correct 1460 ms 112492 KB ans=YES N=66570
19 Correct 816 ms 78256 KB ans=YES N=65421
20 Correct 869 ms 81128 KB ans=YES N=68351
21 Correct 740 ms 76264 KB ans=YES N=67027
22 Correct 963 ms 90500 KB ans=YES N=68879
23 Correct 848 ms 81388 KB ans=YES N=67256

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 61304 KB ans=NO N=1934
2 Correct 44 ms 60672 KB ans=NO N=1965
3 Correct 52 ms 60792 KB ans=YES N=1824
4 Correct 53 ms 60792 KB ans=YES N=1981
5 Correct 51 ms 60792 KB ans=YES N=1814
6 Correct 53 ms 60928 KB ans=YES N=1854
7 Correct 53 ms 60792 KB ans=YES N=1831
8 Correct 53 ms 60920 KB ans=YES N=2000
9 Correct 56 ms 61048 KB ans=YES N=1847
10 Correct 58 ms 61176 KB ans=YES N=1819
11 Correct 54 ms 60792 KB ans=YES N=1986
12 Correct 61 ms 61432 KB ans=YES N=2000
13 Correct 64 ms 61688 KB ans=YES N=1834
14 Correct 61 ms 61560 KB ans=YES N=1860
15 Correct 63 ms 61688 KB ans=YES N=1898
16 Correct 60 ms 61432 KB ans=YES N=1832
17 Correct 67 ms 61944 KB ans=YES N=1929
18 Correct 55 ms 61048 KB ans=YES N=1919
19 Correct 61 ms 61560 KB ans=YES N=1882
20 Correct 67 ms 61944 KB ans=YES N=1922
21 Correct 54 ms 61048 KB ans=YES N=1989
22 Correct 58 ms 61304 KB ans=YES N=1978
23 Correct 57 ms 61304 KB ans=YES N=1867
24 Correct 392 ms 67704 KB ans=NO N=66151
25 Correct 475 ms 89336 KB ans=NO N=64333
26 Correct 736 ms 76740 KB ans=YES N=69316
27 Correct 693 ms 76136 KB ans=YES N=66695
28 Correct 732 ms 76644 KB ans=YES N=68436
29 Correct 753 ms 77160 KB ans=YES N=70000
30 Correct 738 ms 77160 KB ans=YES N=68501
31 Correct 794 ms 78184 KB ans=YES N=70000
32 Correct 793 ms 79772 KB ans=YES N=65009
33 Correct 1176 ms 95440 KB ans=YES N=67007
34 Correct 1255 ms 102740 KB ans=YES N=66357
35 Correct 1368 ms 107692 KB ans=YES N=65430
36 Correct 1359 ms 105676 KB ans=YES N=65790
37 Correct 1282 ms 102384 KB ans=YES N=66020
38 Correct 1258 ms 98280 KB ans=YES N=65809
39 Correct 939 ms 84136 KB ans=YES N=65651
40 Correct 1665 ms 120300 KB ans=YES N=68040
41 Correct 1460 ms 112492 KB ans=YES N=66570
42 Correct 816 ms 78256 KB ans=YES N=65421
43 Correct 869 ms 81128 KB ans=YES N=68351
44 Correct 740 ms 76264 KB ans=YES N=67027
45 Correct 963 ms 90500 KB ans=YES N=68879
46 Correct 848 ms 81388 KB ans=YES N=67256
47 Correct 1939 ms 97756 KB ans=YES N=148315
48 Correct 1183 ms 132088 KB ans=NO N=142745
49 Correct 1010 ms 145788 KB ans=NO N=148443
50 Correct 1877 ms 95204 KB ans=YES N=148328
51 Correct 1876 ms 95608 KB ans=YES N=147855
52 Correct 1933 ms 95764 KB ans=YES N=150000
53 Correct 1898 ms 94508 KB ans=YES N=144725
54 Correct 1903 ms 95664 KB ans=YES N=149445
55 Correct 1864 ms 94848 KB ans=YES N=144455
56 Correct 1792 ms 94556 KB ans=YES N=143487
57 Correct 2071 ms 96528 KB ans=YES N=149688
58 Correct 2932 ms 138208 KB ans=YES N=141481
59 Correct 3400 ms 176900 KB ans=YES N=147430
60 Correct 2346 ms 122332 KB ans=YES N=142247
61 Correct 2870 ms 136444 KB ans=YES N=149941
62 Correct 3145 ms 171980 KB ans=YES N=141635
63 Correct 3233 ms 161776 KB ans=YES N=142896
64 Correct 3474 ms 173284 KB ans=YES N=142069
65 Correct 2057 ms 106768 KB ans=YES N=142378
66 Correct 2719 ms 147196 KB ans=YES N=150000
67 Correct 3457 ms 192156 KB ans=YES N=141452
68 Correct 3158 ms 184148 KB ans=YES N=134453
69 Correct 3005 ms 185828 KB ans=YES N=144172