oj.uz

답안 #545732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545732 2022-04-05T10:01:05 Z leaked Broken Device 2 (JOI22_device2) C++17
0 / 100
 2000 ms 824 KB 
#include "Anna.h"
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

namespace {

int variable_example = 0;

}

int Declare() {
  variable_example++;
  return 11;
}

std::pair<std::vector<int>, std::vector<int> > Anna(long long A) {
//  int j=63-__builtin_clzll(A);
  vec<int> x,y;
  for(int i=10;i>=0;i--){
    if(pw(i)&A) x.pb(1);
    else x.pb(0);
  }
  return make_pair(x,x);
}

#include "Bruno.h"
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
//const int K=17;
namespace {

int variable_example = 0;

}

unordered_map<ll,ll> kek[63];
long long Bruno(std::vector<int> u) {
//    cout<<bitset<10>(20)<<endl;
  variable_example++;
    int n=sz(u)/2;
    vec<int> x(n),y(n);
    vec<int>cnt(n);
    for(int i=0;i<=n;i++) kek[i].clear();
//    vec<ll> kek;
//    unordered_map<ll,ll> kek;
    for(int it=0;it<5e4;it++){
        int f=0,s=0;
        int ok=1;
        ll yo=0;
        for(int t=0;t<n;t++) cnt[t]=0;
        for(int t=0;ok && t<n;t++){
            ++cnt[t];
            if(cnt[t]==5){
                ok=0;
                break;
            }
            if(rand()%2){
                ///f
                if(f<s) ok&=(u[t]==y[f]);
                if(!ok){
                    ok=1;
                    --t;
                    continue;
                }
                x[f]=u[t];
                ++f;
            }
            else{
                if(s<f) ok&=(u[t]==x[s]);
                if(!ok){
                    ok=1;
                    --t;
                    continue;
                }
                y[s]=u[t];
                ++s;
            }
        }
        if(!ok) continue;
        ll vl=0;
        if(f<s){
            for(int j=0;j<s;j++) vl+=pw(s-j-1)*y[j];
            for(int j=f;j<s;j++) yo+=pw(j-f)*(y[j]);
        }
        else{
            for(int j=0;j<f;j++) vl+=pw(f-j-1)*x[j];
            for(int j=s;j<f;j++) yo+=pw(j-s)*(x[j]);
        }
//        cout<<"TO "<<yo<<' '<<vl<<' '<<f<<' '<<s<<endl;
        kek[abs(s-f)][yo]=vl;
//        kek.pb(yo);
    }
    for(int it=0;it<5e4;it++){
        int f=0,s=0;
        int ok=1;
        ll yo=0;
        for(int t=0;t<n;t++) cnt[t]=0;
        for(int t=2*n-1;ok && t>=n;t--){
            ++cnt[t-n];
            if(cnt[t-n]==5){
                ok=0;
                break;
            }
//            cout<<"T "<<t<<' '<<u[t]<<endl;
            if(rand()%2){
                ///f
                if(f<s) ok&=(u[t]==y[f]);
//                cerr<<"FI "<<t<<' '<<u[t]<<endl;
                if(!ok){
                    ok=1;
                    ++t;
                    continue;
                }
//                    cerr<<"FI "<<t<<' '<<u[t]<<endl;

                x[f]=u[t];
                ++f;
            }
            else{
                if(s<f) ok&=(u[t]==x[s]);

                if(!ok){
                    ok=1;
                    ++t;
                    continue;
                }
//                                    cerr<<"SI "<<t<<' '<<u[t]<<endl;

                y[s]=u[t];
                ++s;
            }
        }
        cout<<endl;
        if(!ok) continue;
        reverse(x.begin(),x.begin()+f);
        reverse(y.begin(),y.begin()+s);
//        for(int i=0;i<f;i++) cout<<x[i]<<' ';
//        cout<<endl;
//        for(int i=0;i<s;i++) cout<<y[i]<<' ';
//        cout<<endl;
//        cout<<endl;
//                reverse(x.begin(),x.begin()+f);
//        reverse(y.begin(),y.begin()+s);

        ll vl=0;
        if(f<s){
            for(int j=0;j<f;j++) vl+=pw(f-j-1)*x[j];
            int st=s-f;
            for(int j=0;j<st;j++) yo+=pw(j)*(y[j]);
        }
        else{
            for(int j=0;j<s;j++) vl+=pw(s-j-1)*y[j];
            int st=f-s;
            for(int j=0;j<st;j++) yo+=pw(j)*(x[j]);
        }
        if(kek[abs(s-f)].find(yo)!=kek[abs(s-f)].end()){
//            cout<<"HEY "<<yo<<' '<<vl<<endl;
            return kek[abs(s-f)][yo]*pw(min(f,s))+vl;
        }
//        kek[yo]=vl;
//        kek.pb(yo);
    }
//    cerr<<"BAD "<<endl;
    return -1;
//  return 18;
}
/*
1 0 0 1 0 1 0 1 0 0 0
S F F S  F  F S F S F F
*/

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 516 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 516 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 516 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 516 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 516 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #6
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 824 KB Time limit exceeded
2 Halted 0 ms 0 KB -