oj.uz

답안 #584697

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584697 2022-06-27T20:36:36 Z MohammadAghil 수열 (BOI14_sequence) C++17
0 / 100
 455 ms 212 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pp;

#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define sz(x) (int)x.size()
#define ff first
#define ss secounf 
#define all(x) begin(x), end(x)
#define pb push_back

const ll mod = 1e9+7, maxn = 5e2+1, inf = ll(1e9)+5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll slv(vector<int> a, bool can = true){
     bool ok = false;
     for(int c: a) ok |= c > 0;
     if(!ok) return 0;
     if(sz(a) == 1){
          int x = a[0], res = 0, mn = 0;
          if(x&1){
               mn = 1;
               per(i,10,1) if(x>>i&1) mn = i;
               res = mn*10;
          }
          rep(i,mn+1,10) if(x>>i&1) res = res*10 + i;
          return res;
     }
     // cout << sz(a) << endl;
     ll ans = 10987654321000000ll;
     rep(d,0,10){
          if(d == 9 && !can) break;
          vector<int> b{0};
          bool has_zero = false;
          int cr = d;
          rep(i,0,sz(a)){
               if(a[i]>>cr&1) b.back() |= a[i]^(1<<cr);
               else b.back() |= a[i];
               if(!cr && (a[i]&1)) has_zero = true; 
               cr++;
               if(cr == 10) {
                    cr = 0;
                    if(i - sz(a) + 1) b.pb(0);
               }
          }
          // cout << sz(b) << '\n';
          ll res = slv(b, d != 9 || sz(a) > 2)*10 + d;
          if(!res && has_zero) res = 10;
          ans = min(ans, res);
     }
     return ans;
}



ll slv1(vector<int> a){
     for(int&c: a) c = 1<<c;
     return slv(a);
}

bool chk(int x, int d){
     while(x){
          if(x%10 == d) return true;
          x /= 10;
     }
     return false;
}

ll slv2(vector<int> a){
     rep(i,1,inf){
          bool ok = true;
          rep(j,0,sz(a)) if(!chk(i+j, a[j])){
               ok = false;
               break;
          }
          if(ok) return i;
     }
     return -1;
}

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int n = 3, t = 100000;
     while(t--){
          vector<int> a(n);
          rep(i,0,n) a[i] = rng()%10;
          if(slv1(a) - slv2(a)){
               cout << sz(a) << '\n';
               for(int c: a) cout << c << ' '; cout << '\n';
               cout << slv1(a) << ' ' << slv2(a) << '\n';
               return 0;
          }
     }
     return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:95:16: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |                for(int c: a) cout << c << ' '; cout << '\n';
      |                ^~~
sequence.cpp:95:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |                for(int c: a) cout << c << ' '; cout << '\n';
      |                                                ^~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 444 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 455 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 452 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 448 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -