oj.uz

답안 #824800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
824800 2023-08-14T10:23:02 Z vjudge1 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 2 ms 908 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

int f[20][2][20][100];

int sus(const string &s, int id, bool smaller, int dig, int lst){
   if (f[id][smaller][dig][lst]!=-1) return f[id][smaller][dig][lst];
   if (id==sz(s)) return f[id][smaller][dig][lst]=1;
   int res=0;
   for (int i=0; i<=(smaller?9:s[id]-'0'); ++i){
      if (dig && i==lst%10) continue;
      if (dig>=2 && i==lst/10) continue;
      res+=sus(s, id+1, smaller|(i<s[id]-'0'), dig+(dig || i), (lst%10)*10+i);
   }
   return f[id][smaller][dig][lst]=res;
}

int calc(int x){
   if (x<0) return 0;
   stringstream ss; string s;
   ss << x; ss >> s;
   memset(f, -1, sizeof f);
   return sus(s, 0, 0, 0, 0);
}

void solve(int tc){
   // cout << "Case #" << tc << ": ";
   int l, r; cin >> l >> r;
   cout << calc(r)-calc(l-1);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve(i);
   return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 908 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 2 ms 840 KB Output is correct
20 Correct 1 ms 852 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 840 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 840 KB Output is correct
13 Correct 1 ms 840 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 852 KB Output is correct
18 Correct 2 ms 852 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 2 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 2 ms 852 KB Output is correct
27 Correct 2 ms 852 KB Output is correct
28 Correct 2 ms 852 KB Output is correct
29 Correct 2 ms 852 KB Output is correct
30 Correct 2 ms 852 KB Output is correct
31 Correct 2 ms 852 KB Output is correct
32 Correct 2 ms 852 KB Output is correct
33 Correct 2 ms 852 KB Output is correct
34 Correct 2 ms 852 KB Output is correct
35 Correct 2 ms 852 KB Output is correct
36 Correct 2 ms 852 KB Output is correct
37 Correct 2 ms 840 KB Output is correct
38 Correct 2 ms 852 KB Output is correct
39 Correct 2 ms 852 KB Output is correct
40 Correct 2 ms 852 KB Output is correct
41 Correct 2 ms 840 KB Output is correct
42 Correct 2 ms 840 KB Output is correct
43 Correct 2 ms 852 KB Output is correct
44 Correct 2 ms 852 KB Output is correct
45 Correct 2 ms 852 KB Output is correct