Submission #222822

#	Time	Username	Problem	Language	Result	Execution time	Memory
222822		Autoratch	Palindrome-Free Numbers (BOI13_numbers)	C++14	48.75 / 100	5 ms	384 KiB

numbers

#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++;
    }
    len-=q.size();
    long long ret = 1;
    if(fixed==0) for(int i = 0;i < len;i++)
    {
        if(i==0) ret*=10LL;
        else if(i==1) ret*=9LL;
        else ret*=8LL;
    }
    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--;
    int tm = tmp;
    while(tmp) a = (char)('0'+(tmp%10))+a,tmp/=10;
    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 (stderr)

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: 13.75 / 25
• Subtask 2: 35 / 75