oj.uz

Submission #91686

# Submission time Handle Problem Language Result Execution time Memory
91686 2018-12-29T07:45:04 Z SamAnd Odd-even (IZhO11_oddeven) C++17
100 / 100
 49 ms 504 KB 
#pragma comment(linker,"/STACK:200000000")
#define _CRT_SECURE_NO_WARNINGS
#define mp make_pair
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <cstring>
void fp();
void sp();
using namespace std;
struct ban
{
	vector<short> x;
};
bool operator<(const ban& a,const ban& b)
{
	if(a.x.size()<b.x.size())
		return true;
	if(a.x.size()>b.x.size())
		return false;
	for(int i=0;i<a.x.size();++i)
	{
		if(a.x[i]<b.x[i])
			return true;
		if(a.x[i]>b.x[i])
			return false;
	}
	return false;
}
bool operator==(const ban& a,const ban& b)
{
	if(a.x.size()!=b.x.size())
		return false;
	for(int i=0;i<a.x.size();++i)
		if(a.x[i]!=b.x[i])
			return false;
	return true;
}
bool operator>(const ban& a,const ban& b)
{
	if(!(a<b) && !(a==b))
		return true;
	return false;
}
ban operator+(const ban& q,const ban& p)
{
	ban a=q,b=p;
	reverse(a.x.begin(),a.x.end());
	reverse(b.x.begin(),b.x.end());
	while(a.x.size()!=b.x.size())
	{
		if(a.x.size()<b.x.size())
			a.x.push_back(0);
		else
			b.x.push_back(0);
	}
	int n=a.x.size();
	ban res;
	short x=0;
	for(int i=0;i<n;++i)
	{
		x+=a.x[i];
		x+=b.x[i];
		res.x.push_back(x%10);
		x/=10;
	}
	if(x)
		res.x.push_back(x);
	reverse(res.x.begin(),res.x.end());
	return res;
}
ban operator-(const ban& p,const ban& q)
{
	ban a=p,b=q;
	reverse(a.x.begin(),a.x.end());
	reverse(b.x.begin(),b.x.end());
	while(a.x.size()!=b.x.size())
	{
		if(a.x.size()<b.x.size())
			a.x.push_back(0);
		else
			b.x.push_back(0);
	}
	int n=a.x.size();
	ban res;
	for(int i=0;i<n;++i)
	{
		if(a.x[i]-b.x[i]>=0)
			res.x.push_back(a.x[i]-b.x[i]);
		else
		{
			a.x[i]+=10;
			a.x[i+1]--;
			res.x.push_back(a.x[i]-b.x[i]);
		}
	}
	while(1)
	{
		if(res.x.empty())
			break;
		if(res.x.back())
			break;
		res.x.pop_back();
	}
	reverse(res.x.begin(),res.x.end());
	return res;
}
ban operator*(const ban& a,const ban& b)
{
	ban res;
	int n=a.x.size();
	for(int i=0;i<n;++i)
	{
		ban y;
		for(int j=0;j<a.x[i];++j)
			y=y+b;
		for(int j=0;j<(n-i-1);++j)
			y.x.push_back(0);
		res=res+y;
	}
	return res;
}
ban operator/(const ban& a,const ban& b)
{
	ban res;
	short x=0;
	for(int i=0;i<a.x.size();++i)
	{
		x*=10;
		x+=a.x[i];
		if(x>=2)
		{
			res.x.push_back(x/2);
			x-=((x/2)*2);
		}
		else if(!res.x.empty())
			res.x.push_back(0);
	}
	return res;
}



void tpel(ban a)
{
	for(int i=0;i<a.x.size();++i)
		cout<<a.x[i];
	cout<<endl;
}



ban INF;
ban a1;
ban a2;
ban a4;
ban a;
void sol()
{
	ban l=a1;
	ban r=INF;
	while(a4<(r-l))
	{
		if(!(l==a1))
			cout<<"";
		ban m=(r+l)/a2;
		if((((m*m)+m)/a2)>a)
			r=m;
		else
			l=m;
	}
	ban ans;
	for(ban i=l;(i<r || i==r);i=i+a1)
	{
		ban m=i;
		if((((m*m)+m)/a2)>a)
		{
			m=m-a1;
			i=(((m*m)+m)/a2);
			if(a==i)
				ans=(m*m);
			else
				ans=(m*m)+(a-i-a1)*a2+a1;
			break;
		}
	}
	tpel(ans);
}
int main()
{
	ios_base::sync_with_stdio(false);
	//fp();
	///////////////////////////////////
	string s;
	int n;
	cin>>s;
	n=s.size();
	for(int i=0;i<n;++i)
		a.x.push_back(s[i]-'0');
	////////////////////////////
	a1.x.push_back(1);
	a2.x.push_back(2);
	a4.x.push_back(4);
	INF.x.push_back(1);
	for(int i=0;i<50;++i)
		INF.x.push_back(0);
	///////////////////////////////////
	sol();
	sp();
	return 0;
}

void fp()
{
#ifndef OLYMP
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
}
void sp()
{
#ifdef OLYMP
	system("pause");
#endif
}

Compilation message

oddeven.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker,"/STACK:200000000")
 
oddeven.cpp: In function 'bool operator<(const ban&, const ban&)':
oddeven.cpp:28:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.x.size();++i)
              ~^~~~~~~~~~~
oddeven.cpp: In function 'bool operator==(const ban&, const ban&)':
oddeven.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.x.size();++i)
              ~^~~~~~~~~~~
oddeven.cpp: In function 'ban operator/(const ban&, const ban&)':
oddeven.cpp:134:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.x.size();++i)
              ~^~~~~~~~~~~
oddeven.cpp: In function 'void tpel(ban)':
oddeven.cpp:153:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.x.size();++i)
              ~^~~~~~~~~~~
oddeven.cpp: In function 'void fp()':
oddeven.cpp:223:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("E.in","r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~
oddeven.cpp:224:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("E.out","w",stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct
2 Correct 18 ms 376 KB Output is correct
3 Correct 17 ms 376 KB Output is correct
4 Correct 16 ms 380 KB Output is correct
5 Correct 35 ms 376 KB Output is correct
6 Correct 16 ms 376 KB Output is correct
7 Correct 17 ms 376 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 17 ms 376 KB Output is correct
10 Correct 17 ms 380 KB Output is correct
11 Correct 17 ms 376 KB Output is correct
12 Correct 17 ms 376 KB Output is correct
13 Correct 18 ms 376 KB Output is correct
14 Correct 20 ms 376 KB Output is correct
15 Correct 23 ms 376 KB Output is correct
16 Correct 24 ms 376 KB Output is correct
17 Correct 34 ms 376 KB Output is correct
18 Correct 43 ms 504 KB Output is correct
19 Correct 47 ms 504 KB Output is correct
20 Correct 48 ms 380 KB Output is correct
21 Correct 49 ms 416 KB Output is correct
22 Correct 46 ms 504 KB Output is correct