結果
| 問題 |
No.8055 2019（注：異常な難易度です）
|
| コンテスト | |
| ユーザー |
 もりを
|
| 提出日時 | 2019-04-02 00:09:30 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 16,421 bytes |
| コンパイル時間 | 1,779 ms |
| コンパイル使用メモリ | 184,408 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-27 06:31:10 |
| 合計ジャッジ時間 | 3,671 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 WA * 56 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:38:37: warning: 'digit' may be used uninitialized [-Wmaybe-uninitialized]
38 | #define REPI(i,a,b) for(ll i=ll(a);i<ll(b);++i)
| ^
main.cpp:539:9: note: 'digit' was declared here
539 | ll M, digit;
| ^~~~~
main.cpp:561:7: warning: 'M' may be used uninitialized [-Wmaybe-uninitialized]
561 | if (tmp == M) {
| ^~
main.cpp:539:6: note: 'M' was declared here
539 | ll M, digit;
| ^
ソースコード
#include <bits/stdc++.h>
using namespace std;
//#define int long long
//TEMPLATE START---------------8<---------------8<---------------8<---------------8<---------------//
typedef long long Int;
typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<string> vst; typedef vector<bool> vb; typedef vector<ld> vld; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vector<int> > vvi;
const int INF = (0x7FFFFFFFL); const ll INFF = (0x7FFFFFFFFFFFFFFFL); const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int MOD = 1e9 + 7; const int MODD = 998244353; const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const double PI = acos(-1.0); const double EPS = 1e-9; const string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
int dx[9] = { 1, 0, -1, 0, 1, -1, -1, 1, 0 };
int dy[9] = { 0, 1, 0, -1, -1, -1, 1, 1, 0 };
#define ln '\n'
#define scnaf scanf
#define sacnf scanf
#define sancf scanf
#define SS(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t){cin >> t;}template<typename First, typename...Rest> void MACRO_VAR_Scan(First& first, Rest&...rest){cin >> first;MACRO_VAR_Scan(rest...);}
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
#define SVV(type,c,n,m) vector<vector<type>> c(n,vector<type>(m));for(auto& r:c)for(auto& i:r)cin >> i;
template<class T,class U>ostream &operator<<(ostream &o,const pair<T,U>&j){o<<"{"<<j.first<<", "<<j.second<<"}";return o;}
template<class T,class U>ostream &operator<<(ostream &o,const map<T,U>&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;}
template<class T>ostream &operator<<(ostream &o,const set<T>&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;}
template<class T>ostream &operator<<(ostream &o,const vector<T>&j){o<<"{";for(int i=0;i<(int)j.size();++i)o<<(i>0?", ":"")<<j[i];o<<"}";return o;}
inline int print(void){cout << endl; return 0;}
template<class Head> int print(Head&& head){cout << head;print();return 0;} template<class Head,class... Tail> int print(Head&& head,Tail&&... tail){cout<<head<<" ";print(forward<Tail>(tail)...);return 0;}
inline int debug(void){cerr << endl; return 0;}
template<class Head> int debug(Head&& head){cerr << head;debug();return 0;} template<class Head,class... Tail> int debug(Head&& head,Tail&&... tail){cerr<<head<<" ";debug(forward<Tail>(tail)...);return 0;}
template<typename T> void PA(T &a){int ASIZE=sizeof(a)/sizeof(a[0]);for(int ii=0;ii<ASIZE;++ii){cout<<a[ii]<<" \n"[ii==ASIZE-1];}}
template<typename T> void PV(T &v){int VSIZE=v.size();for(int ii=0;ii<VSIZE;++ii){cout<<v[ii]<<" \n"[ii==VSIZE-1];}}
#define ER(x) cerr << #x << " = " << (x) << endl;
#define ERV(v) {cerr << #v << " : ";for(const auto& xxx : v){cerr << xxx << " ";}cerr << "\n";}
inline int YES(bool x){cout<<((x)?"YES":"NO")<<endl;return 0;} inline int Yes(bool x){cout<<((x)?"Yes":"No")<<endl;return 0;} inline int yes(bool x){cout<<((x)?"yes":"no")<<endl;return 0;}
inline int yES(bool x){cout<<((x)?"yES":"nO")<<endl;return 0;} inline int Yay(bool x){cout<<((x)?"Yay!":":(")<<endl;return 0;}
template<typename A,typename B> void sankou(bool x,A a,B b){cout<<((x)?(a):(b))<<endl;}
#define _overload3(_1,_2,_3,name,...) name
#define _REP(i,n) REPI(i,0,n)
#define REPI(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define REP(...) _overload3(__VA_ARGS__,REPI,_REP,)(__VA_ARGS__)
#define _RREP(i,n) RREPI(i,n,0)
#define RREPI(i,a,b) for(ll i=ll(a);i>=ll(b);--i)
#define RREP(...) _overload3(__VA_ARGS__,RREPI,_RREP,)(__VA_ARGS__)
#define EACH(e,v) for(auto& e : v)
#define PERM(v) sort((v).begin(),(v).end());for(bool c##p=1;c##p;c##p=next_permutation((v).begin(),(v).end()))
#define ADD(a,b) a=(a+ll(b))%MOD
#define MUL(a,b) a=(a*ll(b))%MOD
inline ll MOP(ll x,ll n,ll m=MOD){ll r=1;while(n>0){if(n&1)(r*=x)%=m;(x*=x)%=m;n>>=1;}return r;}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}inline ll POW(ll a,ll b){ll c=1ll;do{if(b&1)c*=1ll*a;a*=1ll*a;}while(b>>=1);return c;}
template<typename T,typename A,typename B> inline bool between(T x,A a,B b) {return ((a<=x)&&(x<b));}template<class T> inline T sqr(T x){return x*x;}
template<typename A,typename B> inline bool chmax(A &a,const B &b){if(a<b){a=b;return 1;}return 0;}
template<typename A,typename B> inline bool chmin(A &a,const B &b){if(a>b){a=b;return 1;}return 0;}
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort((v).begin(),(v).end())
#define RSORT(v) sort((v).rbegin(),(v).rend())
#define EXIST(s,e) (find((s).begin(),(s).end(),(e))!=(s).end())
#define EXISTST(s,c) (((s).find(c))!=string::npos)
#define POSL(x,val) (lower_bound(x.begin(),x.end(),val)-x.begin())
#define POSU(x,val) (upper_bound(x.begin(),x.end(),val)-x.begin())
#define GEQ(x,val) (int)(x).size() - POSL((x),(val))
#define GREATER(x,val) (int)(x).size() - POSU((x),(val))
#define LEQ(x,val) POSU((x),(val))
#define LESS(x,val) POSL((x),(val))
#define SZV(a) int((a).size())
#define SZA(a) sizeof(a)/sizeof(a[0])
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMINF(a) memset(a,0x3f,sizeof(a))
#define FILL(a,b) memset(a,b,sizeof(a))
#define UNIQUE(v) sort((v).begin(),(v).end());(v).erase(unique((v).begin(),(v).end()),(v).end())
struct abracadabra{
abracadabra(){
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(20);
cerr << fixed << setprecision(5);
};
} ABRACADABRA;
//TEMPLATE END---------------8<---------------8<---------------8<---------------8<---------------//
namespace FFT{
using dbl = double;
struct num{
dbl x,y;
num(){x=y=0;}
num(dbl x,dbl y):x(x),y(y){}
};
inline num operator+(num a,num b){
return num(a.x+b.x,a.y+b.y);
}
inline num operator-(num a,num b){
return num(a.x-b.x,a.y-b.y);
}
inline num operator*(num a,num b){
return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
inline num conj(num a){
return num(a.x,-a.y);
}
int base=1;
vector<num> rts={{0,0},{1,0}};
vector<int> rev={0,1};
const dbl PI=acosl(-1.0);
void ensure_base(int nbase){
if(nbase<=base) return;
rev.resize(1<<nbase);
for(int i=0;i<(1<<nbase);i++)
rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1));
rts.resize(1<<nbase);
while(base<nbase){
dbl angle=2*PI/(1<<(base+1));
for(int i=1<<(base-1);i<(1<<base);i++){
rts[i<<1]=rts[i];
dbl angle_i=angle*(2*i+1-(1<<base));
rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i));
}
base++;
}
}
void fft(vector<num> &a,int n=-1){
if(n==-1) n=a.size();
assert((n&(n-1))==0);
int zeros=__builtin_ctz(n);
ensure_base(zeros);
int shift=base-zeros;
for(int i=0;i<n;i++)
if(i<(rev[i]>>shift))
swap(a[i],a[rev[i]>>shift]);
for(int k=1;k<n;k<<=1){
for(int i=0;i<n;i+=2*k){
for(int j=0;j<k;j++){
num z=a[i+j+k]*rts[j+k];
a[i+j+k]=a[i+j]-z;
a[i+j]=a[i+j]+z;
}
}
}
}
vector<num> fa;
template<typename T>
vector<Int> multiply(const vector<T> &a,const vector<T> &b){
int need=a.size()+b.size()-1;
int nbase=0;
while((1<<nbase)<need) nbase++;
ensure_base(nbase);
int sz=1<<nbase;
if(sz>(int)fa.size()) fa.resize(sz);
for(int i=0;i<sz;i++){
int x=(i<(int)a.size()?a[i]:0);
int y=(i<(int)b.size()?b[i]:0);
fa[i]=num(x,y);
}
fft(fa,sz);
num r(0,-0.25/sz);
for(int i=0;i<=(sz>>1);i++){
int j=(sz-i)&(sz-1);
num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r;
if(i!=j)
fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r;
fa[i]=z;
}
fft(fa,sz);
vector<Int> res(need);
for(int i=0;i<need;i++)
res[i]=fa[i].x+0.5;
return res;
}
};
struct bigint {
using ll = long long;
using vll = vector<ll>;
constexpr static ll base = 1000000000;
constexpr static ll base_digits = 9;
vll a;
ll sign;
bigint():sign(1){}
bigint(ll v){*this=v;}
bigint(const string &s){read(s);}
void operator=(const bigint &v){
sign=v.sign;
a=v.a;
}
void operator=(ll v){
sign=1;
if(v<0) sign=-1,v=-v;
for(;v>0;v=v/base) a.push_back(v%base);
}
bigint operator+(const bigint &v) const{
if(sign==v.sign){
bigint res=v;
for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size())||carry;++i){
if(i==(ll)res.a.size()) res.a.push_back(0);
res.a[i]+=carry+(i<(ll)a.size()?a[i]:0);
carry=res.a[i]>=base;
if(carry) res.a[i]-=base;
}
return res;
}
return *this -(-v);
}
bigint operator-(const bigint &v) const{
if(sign==v.sign){
if(abs()>=v.abs()){
bigint res=*this;
for(ll i=0,carry=0;i<(ll)v.a.size()||carry;++i){
res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0);
carry=res.a[i]<0;
if(carry) res.a[i]+=base;
}
res.trim();
return res;
}
return -(v-*this);
}
return *this+(-v);
}
void operator*=(ll v){
if(v<0) sign=-sign,v=-v;
for(ll i=0,carry=0;i<(ll)a.size()|| carry;++i){
if(i ==(ll)a.size()) a.push_back(0);
ll cur=a[i] *(ll)v+carry;
carry=(ll)(cur/base);
a[i]=(ll)(cur%base);
// asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base));
}
trim();
}
bigint operator*(ll v) const{
bigint res=*this;
res *=v;
return res;
}
friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){
ll norm=base/(b1.a.back()+1);
bigint a=a1.abs()*norm;
bigint b=b1.abs()*norm;
bigint q,r;
q.a.resize(a.a.size());
for(ll i=a.a.size()-1;i>=0;i--){
r *=base;
r+=a.a[i];
ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()];
ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1];
ll d=((ll)base*s1+s2)/b.a.back();
r-=b*d;
while(r<0) r+=b,--d;
q.a[i]=d;
}
q.sign=a1.sign*b1.sign;
r.sign=a1.sign;
q.trim();
r.trim();
return make_pair(q,r/norm);
}
bigint operator/(const bigint &v) const{
return divmod(*this,v).first;
}
bigint operator%(const bigint &v) const{
return divmod(*this,v).second;
}
void operator/=(ll v){
if(v<0) sign=-sign,v=-v;
for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){
ll cur=a[i]+rem *(ll)base;
a[i]=(ll)(cur/v);
rem=(ll)(cur%v);
}
trim();
}
bigint operator/(ll v) const{
bigint res=*this;
res/=v;
return res;
}
ll operator%(ll v) const{
if(v<0) v=-v;
ll m=0;
for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m *(ll)base)%v;
return m*sign;
}
void operator+=(const bigint &v){
*this=*this+v;
}
void operator-=(const bigint &v){
*this=*this-v;
}
void operator*=(const bigint &v){
*this=*this*v;
}
void operator/=(const bigint &v){
*this=*this/v;
}
bool operator<(const bigint &v) const{
if(sign!=v.sign) return sign<v.sign;
if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign;
for(ll i=a.size()-1;i>=0;i--)
if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign;
return false;
}
bool operator>(const bigint &v) const{
return v<*this;
}
bool operator<=(const bigint &v) const{
return !(v<*this);
}
bool operator>=(const bigint &v) const{
return !(*this<v);
}
bool operator==(const bigint &v) const{
return !(*this<v)&&!(v<*this);
}
bool operator!=(const bigint &v) const{
return *this<v|| v<*this;
}
void trim(){
while(!a.empty()&&!a.back()) a.pop_back();
if(a.empty()) sign=1;
}
bool isZero() const{
return a.empty()||(a.size()==1&&!a[0]);
}
bigint operator-() const{
bigint res=*this;
res.sign=-sign;
return res;
}
bigint abs() const{
bigint res=*this;
res.sign*=res.sign;
return res;
}
ll longValue() const{
ll res=0;
for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i];
return res*sign;
}
friend bigint gcd(const bigint &a,const bigint &b){
return b.isZero() ? a : gcd(b,a%b);
}
friend bigint lcm(const bigint &a,const bigint &b){
return a/gcd(a,b)*b;
}
void read(const string &s){
sign=1;
a.clear();
ll pos=0;
while(pos<(ll)s.size()&&(s[pos]=='-'|| s[pos]=='+')){
if(s[pos]=='-') sign=-sign;
++pos;
}
for(ll i=s.size()-1;i>=pos;i-=base_digits){
ll x=0;
for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0';
a.push_back(x);
}
trim();
}
friend istream &operator>>(istream &stream,bigint &v){
string s;
stream>>s;
v.read(s);
return stream;
}
friend ostream &operator<<(ostream &stream,const bigint &v){
if(v.sign==-1) stream<<'-';
stream<<(v.a.empty()?0:v.a.back());
for(ll i=(ll)v.a.size()-2;i>=0;--i)
stream<<setw(base_digits)<<setfill('0')<<v.a[i];
return stream;
}
static vll convert_base(const vll &a,ll old_digits,ll new_digits){
vll p(max(old_digits,new_digits)+1);
p[0]=1;
for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10;
vll res;
ll cur=0;
ll cur_digits=0;
for(ll i=0;i<(ll)a.size();i++){
cur+=a[i]*p[cur_digits];
cur_digits+=old_digits;
while(cur_digits>=new_digits){
res.push_back(signed(cur%p[new_digits]));
cur/=p[new_digits];
cur_digits-=new_digits;
}
}
res.push_back((signed)cur);
while(!res.empty()&&!res.back()) res.pop_back();
return res;
}
static vll karatsubaMultiply(const vll &a,const vll &b){
ll n=a.size();
vll res(n+n);
if(n<=32){
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++)
res[i+j]+=a[i]*b[j];
return res;
}
ll k=n>>1;
vll a1(a.begin(),a.begin()+k);
vll a2(a.begin()+k,a.end());
vll b1(b.begin(),b.begin()+k);
vll b2(b.begin()+k,b.end());
vll a1b1=karatsubaMultiply(a1,b1);
vll a2b2=karatsubaMultiply(a2,b2);
for(ll i=0;i<k;i++) a2[i]+=a1[i];
for(ll i=0;i<k;i++) b2[i]+=b1[i];
vll r=karatsubaMultiply(a2,b2);
for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i];
for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i];
for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i];
for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i];
for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i];
return res;
}
bigint operator*(const bigint &v) const{
constexpr static ll nbase = 10000;
constexpr static ll nbase_digits = 4;
vll a=convert_base(this->a,base_digits,nbase_digits);
vll b=convert_base(v.a,base_digits,nbase_digits);
/*
while(a.size()<b.size()) a.push_back(0);
while(b.size()<a.size()) b.push_back(0);
while(a.size() &(a.size()-1)) a.push_back(0),b.push_back(0);
vll c=karatsubaMultiply(a,b);
*/
if(a.empty()) a.push_back(0);
if(b.empty()) b.push_back(0);
vll c=FFT::multiply(a,b);
bigint res;
res.sign=sign*v.sign;
for(ll i=0,carry=0;i<(ll)c.size();i++){
ll cur=c[i]+carry;
res.a.push_back((ll)(cur%nbase));
carry=(ll)(cur/nbase);
if(i+1==(int)c.size()&&carry>0) c.push_back(0);
}
res.a=convert_base(res.a,nbase_digits,base_digits);
res.trim();
return res;
}
};
const int MAX_BIT = 18;
void out(int _1, int _2, int _3) {
// print(_1, _2, _3);
bigint res = 0;
REP(i, _1 + _2 + _3) {
res *= 2;
if (i < _1 || i >= _1 + _2) {
res += 1;
}
}
print(res);
}
signed main() {
SS(ll, N);
ll tmp = 0;
ll M, digit;
REP(i, MAX_BIT) {
tmp += i * (i - 1) / 2 + 1;
if (tmp == N) {
out(i + 1, 0, 0);
return 0;
}
if (tmp > N) {
digit = i + 1;
break;
}
M = N - tmp;
}
// 初期状態: 1がdigit個ならんでいる
REP(l, 1, digit) {
REP(r, l + 1, digit) {
int _1 = l;
int _2 = r - l;
int _3 = digit - r;
ll tmp = _3 + (_2 + _3 - 1) * (_1 - 1) + _1 * (_1 - 1) / 2;
// print(_1, _2, _3, tmp);
if (tmp == M) {
out(_1, _2, _3);
return 0;
}
}
}
// debug(M, digit);
}