Submission #1045619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045619		ezzzay	Odd-even (IZhO11_oddeven)	C++14	100 / 100	152 ms	432 KiB

oddeven

#include<bits/stdc++.h>
using namespace std;
#define int  long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
string fix(string s){
    int i=0;
    for(1;i<s.size();i++){
        if(s[i]!='0'){
            break;
        }
    }
    string s2;
    for(int j=i;j<s.size();j++){
        s2+=s[j];
    }
    return s2;
}
string sum(string s, string s2){
    if(s2.size()>s.size()){string h=s;s=s2;s2=h;}int p=s.size()-s2.size();
    for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
    int n=s.size(),m=s2.size(),k;int i=n-1,j=m-1;
    while(1){int a=s[i]-'0';int b=0;if(j>=0)b=s2[j]-'0';
        if((a+b+c)>9){k=(a+b+c)%10;c=1;}
        else{k=a+b+c;c=0;}char p=k+'0';ans=p+ans;
        if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
    return fix(ans);
}
string multi(string s, string s2){ 
    string ans="0";int n=s.size();int m=s2.size();int l=0;
    for(int i=n-1;i>=0;i--){string pre;int c=0;for(int j=m-1;j>=0;j--){
    int a=s[i]-'0',b=s2[j]-'0';int k=(a*b+c)%10;char p=k+'0';pre=p+pre;c=(a*b+c)/10;
        }
        if(c!=0){
            char p=c+'0';
            pre=p+pre;
        }
        for(int j=0;j<l;j++){
            pre=pre+'0';
        }
        l++;
        ans=sum(ans,pre);
    }
    return fix(ans);
}
string divide(string s){ 
    string ans;int c=0;
    for(int i=0;i<s.size();i++){int a=s[i]-'0';int k=c*10+a;
    char p=(k/2)+'0';
        c=k%2;ans=ans+p;
    }return fix(ans);
}
int check(string s, string s2){
    if(s.size()>s2.size())return 0;
    else if(s.size()<s2.size())return 1;
    else {
        if(s>s2 )return 0;
        else return 1;
    }
    
}

bool isSmaller(string str1, string str2) 
{ 
    // Calculate lengths of both string 
    int n1 = str1.length(), n2 = str2.length(); 
  
    if (n1 < n2) 
        return true; 
    if (n2 < n1) 
        return false; 
  
    for (int i = 0; i < n1; i++) 
        if (str1[i] < str2[i]) 
            return true; 
        else if (str1[i] > str2[i]) 
            return false; 
  
    return false; 
} 
  
// Function for find difference of larger numbers 
string findDiff(string str1, string str2) 
{ 
    // Before proceeding further, make sure str1 
    // is not smaller 
    if (isSmaller(str1, str2)) 
        swap(str1, str2); 
  
    // Take an empty string for storing result 
    string str = ""; 
  
    // Calculate length of both string 
    int n1 = str1.length(), n2 = str2.length(); 
  
    // Reverse both of strings 
    reverse(str1.begin(), str1.end()); 
    reverse(str2.begin(), str2.end()); 
  
    int carry = 0; 
  
    // Run loop till small string length 
    // and subtract digit of str1 to str2 
    for (int i = 0; i < n2; i++) { 
        // Do school mathematics, compute difference of 
        // current digits 
  
        int sub 
            = ((str1[i] - '0') - (str2[i] - '0') - carry); 
  
        // If subtraction is less than zero 
        // we add then we add 10 into sub and 
        // take carry as 1 for calculating next step 
        if (sub < 0) { 
            sub = sub + 10; 
            carry = 1; 
        } 
        else
            carry = 0; 
  
        str.push_back(sub + '0'); 
    } 
  
    // subtract remaining digits of larger number 
    for (int i = n2; i < n1; i++) { 
        int sub = ((str1[i] - '0') - carry); 
  
        // if the sub value is -ve, then make it positive 
        if (sub < 0) { 
            sub = sub + 10; 
            carry = 1; 
        } 
        else
            carry = 0; 
  
        str.push_back(sub + '0'); 
    } 
  
    // reverse resultant string 
    reverse(str.begin(), str.end()); 
  
    return str; 
} 
  string sq(string a){
    string lo="0";
    string hi="1";
    for(int i=1;i<=102;i++){
        hi+='0';
    }
    while(check(lo,hi)){
        string mid=sum(lo,hi);
        mid=(divide(mid));
        string t=multi(mid,mid);
        if(check(a,t)==0){
            lo=sum(mid,"1");
        }
        else{
            hi=findDiff(mid,"1");
        }
    }
    if(multi(lo,lo)==a){
        return lo;
    }
    else{
        return hi;
    }
    return lo;
}
signed main(){
    string n;
    cin>>n;
    
    string h=sq(multi(n,"2"));
   
    
    //cout<<divide(multi(h,(sum(h,"1"))));
    
    if( isSmaller(divide(multi(h,(sum(h,"1")))),n) )h=sum(h,"1");
  
    cout<<fix(findDiff(multi(h,h), multi( findDiff( divide(multi(h,sum(h,"1"))),n ),"2" ) ));
    
}

Compilation message (stderr)

oddeven.cpp: In function 'std::string fix(std::string)':
oddeven.cpp:10:9: warning: statement has no effect [-Wunused-value]
   10 |     for(1;i<s.size();i++){
      |         ^
oddeven.cpp:10:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(1;i<s.size();i++){
      |           ~^~~~~~~~~
oddeven.cpp:16:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int j=i;j<s.size();j++){
      |                 ~^~~~~~~~~
oddeven.cpp: In function 'std::string sum(std::string, std::string)':
oddeven.cpp:23:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |     for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
      |     ^~~
oddeven.cpp:23:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |     for(int i=0;i<p;i++)s2="0"+s2;string ans;int c=0;
      |                                   ^~~~~~
oddeven.cpp:28:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |         if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
      |         ^~
oddeven.cpp:28:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |         if(i==0)break;i--;j--;}if(c==1){ans="1"+ans;}
      |                       ^
oddeven.cpp: In function 'std::string divide(std::string)':
oddeven.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0;i<s.size();i++){int a=s[i]-'0';int k=c*10+a;
      |                 ~^~~~~~~~~

• Subtask 1: 100 / 100