Submission #1184432

#TimeUsernameProblemLanguageResultExecution timeMemory
1184432sasdePalindrome-Free Numbers (BOI13_numbers)C++20
100 / 100
1 ms532 KiB
#include<bits/stdc++.h> #define task "strdel" #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace using namespace std; const int N=1e6+5,lg=20,mod=1e9+7; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } string a,b; bool ok(string a){ for(int i=0;i<a.size();++i){ if(i+2<a.size()){ if(a[i]==a[i+2])return false; } if(i+1<a.size()){ if(a[i]==a[i+1])return false; } } return true; } int n; string s; long long f[20][2][12][12]; long long cc(int i,bool ok,int last,int last2){ if(i>n)return 1; long long res=f[i][ok][last][last2]; if(res!=-1)return res; res=0; for(int j=0;j<=9;++j) if(ok||s[i]>=j+'0'){ // cout <<i<<" "<<j<<" "<<last<<" "<<last2<<'\n'; if(last!=11){ if(j!=last&&j!=last2){ res+=cc(i+1,ok||s[i]>j+'0',j,last); } } else{ if(j==0){ res+=cc(i+1,ok||s[i]>j+'0',last,last2); } else{ res+=cc(i+1,ok||s[i]>j+'0',j,last); } } } return f[i][ok][last][last2]=res; } long long solve(string b){ b=" "+b; s=b; n=b.size()-1; memset(f,-1,sizeof f); // cout <<s<<" "<<cc(1,false,11,11)<<'\n'; return cc(1,false,11,11); } void solve(){ cin >> a >> b; cout <<solve(b)-solve(a)+ok(a); } main() { srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin >> t; while(t--){ solve(); cout<<'\n'; } }

Compilation message (stderr)

numbers.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main()
      | ^~~~
numbers.cpp: In function 'int main()':
numbers.cpp:83:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:84:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...