Submission #673748

#TimeUsernameProblemLanguageResultExecution timeMemory
673748yeetholmes619Palindrome-Free Numbers (BOI13_numbers)C++17
100 / 100
2 ms436 KiB
//Author = Anirudh Srikanth (yeetholmes619) [B20CS006] //https://github.com/yeetholmes619/Template.git #include<bits/stdc++.h> #define curtime chrono::high_resolution_clock::now() #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define timedif(start,end) chrono::duration_cast<chrono::nanoseconds>(end - start).count() using namespace std; #define RESET "\033[0m" #define BR "\033[1m\033[31m" /* Bold Red */ #define BG "\033[1m\033[32m" /* Bold Green */ #define BB "\033[1m\033[34m" /* Bold Blue */ #define ll long long #define ld long double #define INF 1000000007 #define pb push_back #define pf push_front #define FOR(i,a,b) for(int i = a; i <= b; i++) #define ROF(i,a,b) for(int i = a; i >= b; i--) #define vi vector<int> #define vvi vector<vector<int>> #define vpii vector<pair<int,int>> #define pii pair<int,int> #define mii map<int,int> #define mci map<char,int> template <typename T> using matrix = vector<vector<T>>; //as seen on https://codeforces.com/profile/I_love_Tanya_Romanova 's template //in order to be able to use pre-defined variables in STL #define y0 sdkfaslhagaklsldk #define y1 aasdfasdfasdf #define yn askfhwqriuperikldjk #define j1 assdgsdgasghsf #define tm sdfjahlfasfh #define lr asgasgash #define norm asdfasdgasdgsd #define left asdgashgrketwjklrej #define have adsgagshdshfhds #define ends asdgahhfdsfshdshfd #define prev asdgSHJsfgsdfhdsh #define umap unordered_map #define sz(x) (int)(x.size()) #define mp make_pair #define allvec(v) v.begin(), v.end() #define int long long #define output(value) cout << value << "\n" #define error(errorString) cout << BR << errorString << RESET<< "\n" #define info(infoString) cout << BB << infoString << RESET << "\n" #define success(successString) cout << BB << successString << RESET << "\n" #define allarr(a,n) a, a+n const int mod1 =1000000007; const int mod2 = 998244353; // precedence order :- double > float > long long int > long int > int > char // remember that boolean arrays and variables if uninitialized are given false // say x is a character, s += x is faster than s = s+x //Check if constraints are correct // for single arrays declare them as long long int //overflow must be taken care of!! use strings when big // 0 < |int| < 1e9 // 0 < |long long int| < 1e18 //when you are working with stacks, remember to take care of stacks of 0 size //when you see a problem, and you know how you would tackle it in the real world, but don't know how //you would do it in code, go step by step, in each step try to be concious of what you want to do //and once you have done so, review through and remember what data structure would be perfect //when we pass an array in a function the pointer is passed but when we pass a vector, a copy is passed template<typename T1, typename T2> // cin >> pair<T1, T2> istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); } template<typename T> // cin >> vector<T> istream& operator>>(istream &istream, vector<T> &v) { for (auto &it : v) cin >> it; return istream; } template<typename T1, typename T2> // cout << pair<T1, T2> ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); } template<typename T> // cout << vector<T> ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; } //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\DEBUG/\/\/\/\/\/\/\/\/\/\/\/\///\/\/ void __print(int32_t x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n"<<RESET;} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef DEBUG #define debug(x...) cerr <<BR<< "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\///\/\/\/\/\/\/ //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\GLOBAL VARIABLES/\/\/\/\/\/\/\/\/\/\/\/\///\/\/ int l,r; int dp[20][11][11][2][2]; //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\///\/\/\/\/\/\/ void reset(){ for(int i = 0; i < 20; i++) for(int j = 0; j < 11; j++) for(int k = 0; k < 11; k++) for(int l = 0; l < 2; l++) for(int m = 0; m < 2; m++) dp[i][j][k][l][m] = -1; } int solve(int c, int pos = 0, int last2 = 10, int last1 = 10, int valid = 0, int smaller =0){ debug(c,pos,last2,last1,valid,smaller); int &ref = dp[pos][last2][last1][valid][smaller]; if(ref != -1) return ref; int len = to_string(c).size(); if(pos == len) return ref = 1; ref = 0; int limit = 9; if(!smaller){ limit = to_string(c)[pos] - '0'; } for(int dig = 0; dig <= limit; dig++){ if(last1 == dig or last2 == dig) continue; int ndig = dig; int nvalid = valid; if(!valid){ nvalid = (pos+1 == len or dig > 0); } if(!nvalid){ ndig = 10; } ref += solve(c,pos+1,last1,ndig,nvalid,(smaller) ? true : (dig != limit)); } return ref; } void take(){ cin>>l>>r; } void solve(){ take(); reset(); int total = solve(r); reset(); cout<<total - solve(l-1)<<"\n"; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); auto time0 = curtime; ll t = 1; for(int i = 1 ; i <= t; i++) { //cout << "Case #" << i << ": "; solve(); } #ifdef YEET cerr<<"Execution Time: "<<timedif(time0,curtime)*1e-9<<" sec\n"; #endif return 0; }

Compilation message (stderr)

numbers.cpp: In function 'int32_t main()':
numbers.cpp:171:10: warning: variable 'time0' set but not used [-Wunused-but-set-variable]
  171 |     auto time0 = curtime;
      |          ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...