oj.uz

답안 #222842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222842 2020-04-14T07:19:58 Z Autoratch Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 6 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

string a,b;
deque<int> q;
long long tmp,resa,resb;

long long solve(int len)
{
    int fixed = 0;
    bool fix = false;
    for(int i = 0;i < q.size();i++)
    {
        if(i>0){ if(fix and q[i]==q[i-1]) return 0; }
        if(i>1){ if(fix and q[i]==q[i-2]) return 0; }
        if(!fix and q[i]) fix = true;
        if(fix) fixed++;
    }
    int lenn = len;
    len-=q.size();
    long long ret = 1;
    if(fixed==0)
    {
        for(int i = 0;i < len;i++)
        {
            if(i==0) ret*=9LL;
            else if(i==1) ret*=9LL;
            else ret*=8LL;
        }
        for(int i = 0;i < len-1;i++)
        {
            q.push_back(0);
            for(int j = 1;j <= 9;j++) q.push_back(j),ret+=solve(lenn),q.pop_back();
        }
        if(len>0) ret++;
        for(int i = 0;i < len-1;i++) q.pop_back();
    }
    else if(fixed==1) for(int i = 0;i < len;i++)
    {
        if(i==0) ret*=9LL;
        else ret*=8LL;
    }
    else for(int i = 0;i < len;i++) ret*=8LL;
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> tmp >> b; 
    tmp--;
    long long tm = tmp;
    while(tmp) a = (char)('0'+(tmp%10LL))+a,tmp/=10LL;
    if(tm>=0)
    {
    if(a.length()==0) a+='0';
    for(char c : a)
    {
        int x = c-'0';
        for(int i = 0;i < x;i++) q.push_back(i),resa+=solve(a.length()),q.pop_back();
        q.push_back(x);
    }
    resa+=solve(a.length());
    }
    while(!q.empty()) q.pop_back();
    for(char c : b)
    {
        int x = c-'0';
        for(int i = 0;i < x;i++) q.push_back(i),resb+=solve(b.length()),q.pop_back();
        q.push_back(x);
    }
    resb+=solve(b.length());
    cout << resb-resa;
}

Compilation message

numbers.cpp: In function 'long long int solve(int)':
numbers.cpp:12:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < q.size();i++)
                   ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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