提出 #69714289

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=(a);i<(n);i++)
#define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

namespace fastIO{ 
	#define BUF_SIZE 100000 
	#define OUT_SIZE 100000 
	#define ll long long 
	//fread->read 
	bool IOerror=0; 
	inline char nc(){ 
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; 
		if (p1==pend){ 
			p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); 
			if (pend==p1){IOerror=1;return -1;} 
			//{printf("IO error!\n");system("pause");for (;;);exit(0);} 
		} 
		return *p1++; 
	} 
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} 
	inline void read(int &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(ll &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (sign)x=-x; 
	} 
	inline void read(double &x){ 
		bool sign=0; char ch=nc(); x=0; 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		if (ch=='-')sign=1,ch=nc(); 
		for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; 
		if (ch=='.'){ 
			double tmp=1; ch=nc(); 
			for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); 
		} 
		if (sign)x=-x; 
	} 
	inline void read(char *s){ 
		char ch=nc(); 
		for (;blank(ch);ch=nc()); 
		if (IOerror)return; 
		for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; 
		*s=0; 
	} 
	inline void read(char &c){ 
		for (c=nc();blank(c);c=nc()); 
		if (IOerror){c=-1;return;} 
	} 
	//getchar->read 
	inline void read1(int &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(ll &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (bo)x=-x; 
	} 
	inline void read1(double &x){ 
		char ch;int bo=0;x=0; 
		for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; 
		for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); 
		if (ch=='.'){ 
			double tmp=1; 
			for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar()); 
		} 
		if (bo)x=-x; 
	} 
	inline void read1(char *s){ 
		char ch=getchar(); 
		for (;blank(ch);ch=getchar()); 
		for (;!blank(ch);ch=getchar())*s++=ch; 
		*s=0; 
	} 
	inline void read1(char &c){for (c=getchar();blank(c);c=getchar());} 
	//scanf->read 
	inline void read2(int &x){scanf("%d",&x);} 
	inline void read2(ll &x){ 
		#ifdef _WIN32 
			scanf("%I64d",&x); 
		#else 
		#ifdef __linux 
			scanf("%lld",&x); 
		#else 
			puts("error:can't recognize the system!"); 
		#endif 
		#endif 
	} 
	inline void read2(double &x){scanf("%lf",&x);} 
	inline void read2(char *s){scanf("%s",s);} 
	inline void read2(char &c){scanf(" %c",&c);} 
	//inline void readln2(char *s){gets(s);} 
	//fwrite->write 
	struct Ostream_fwrite{ 
		char *buf,*p1,*pend; 
		Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} 
		void out(char ch){ 
			if (p1==pend){ 
				fwrite(buf,1,BUF_SIZE,stdout);p1=buf; 
			} 
			*p1++=ch; 
		} 
		void print(int x){ 
			static char s[15],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); 
		} 
		void println(int x){ 
			static char s[15],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); out('\n'); 
		} 
		void print(ll x){ 
			static char s[25],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); 
		} 
		void println(ll x){ 
			static char s[25],*s1;s1=s; 
			if (!x)*s1++='0';if (x<0)out('-'),x=-x; 
			while(x)*s1++=x%10+'0',x/=10; 
			while(s1--!=s)out(*s1); out('\n'); 
		} 
		void print(double x,int y){ 
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000, 
				1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL, 
				100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL}; 
			if (x<-1e-12)out('-'),x=-x;x*=mul[y]; 
			ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1; 
			ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2); 
			if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];++i) out('0'); print(x3);} 
		} 
		void println(double x,int y){print(x,y);out('\n');} 
		void print(char *s){while (*s)out(*s++);} 
		void println(char *s){while (*s)out(*s++);out('\n');} 
		void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} 
		~Ostream_fwrite(){flush();} 
	}Ostream; 
	inline void print(int x){Ostream.print(x);} 
	inline void println(int x){Ostream.println(x);} 
	inline void print(char x){Ostream.out(x);} 
	inline void println(char x){Ostream.out(x);Ostream.out('\n');} 
	inline void print(ll x){Ostream.print(x);} 
	inline void println(ll x){Ostream.println(x);} 
	inline void print(double x,int y){Ostream.print(x,y);} 
	inline void println(double x,int y){Ostream.println(x,y);} 
	inline void print(char *s){Ostream.print(s);} 
	inline void println(char *s){Ostream.println(s);} 
	inline void println(){Ostream.out('\n');} 
	inline void flush(){Ostream.flush();} 
	//puts->write 
	char Out[OUT_SIZE],*o=Out; 
	inline void print1(int x){ 
		static char buf[15]; 
		char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; 
		while(x)*p1++=x%10+'0',x/=10; 
		while(p1--!=buf)*o++=*p1; 
	} 
	inline void println1(int x){print1(x);*o++='\n';} 
	inline void print1(ll x){ 
		static char buf[25]; 
		char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; 
		while(x)*p1++=x%10+'0',x/=10; 
		while(p1--!=buf)*o++=*p1; 
	} 
	inline void println1(ll x){print1(x);*o++='\n';} 
	inline void print1(char c){*o++=c;} 
	inline void println1(char c){*o++=c;*o++='\n';} 
	inline void print1(char *s){while (*s)*o++=*s++;} 
	inline void println1(char *s){print1(s);*o++='\n';} 
	inline void println1(){*o++='\n';} 
	inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}} 
	struct puts_write{ 
		~puts_write(){flush1();} 
	}_puts; 
	inline void print2(int x){printf("%d",x);} 
	inline void println2(int x){printf("%d\n",x);} 
	inline void print2(char x){printf("%c",x);} 
	inline void println2(char x){printf("%c\n",x);} 
	inline void print2(ll x){ 
		#ifdef _WIN32 
			printf("%I64d",x); 
		#else 
		#ifdef __linux 
			printf("%lld",x); 
		#else 
			puts("error:can't recognize the system!"); 
		#endif 
		#endif 
	} 
	inline void println2(ll x){print2(x);printf("\n");} 
	inline void println2(){printf("\n");} 
	#undef ll 
	#undef OUT_SIZE 
	#undef BUF_SIZE 
}; 
using namespace fastIO; 

const int N=251000;
ll d[N],a[N],L,R;
int n;
bool hascycle(ll m)  {
	rep(i,0,n) d[i]=a[i];
	int l=0,r=n-1;
	ll off=0;
	while (r>=0&&d[r]>=m) --r;
	while (true) {
		if (r<=l) return false;
		if (r-l==1) {
			R=min(R,off+d[l]+d[l+1]-gcd(d[l],d[l+1]))+1;
			return m>d[l]+d[l+1]-gcd(d[l],d[l+1]);
		}
		if (2*d[l]>=m) {
			rep(i,l+1,r+1) d[i]-=d[l];
			m-=d[l];
			off+=d[l];
			l++;
		} else {
			ll N=d[l]+m%d[l];
			if (d[l]+d[l+1]<=m) {
				R=min(d[l]+d[l+1]+off,R);
				return true;
			}
			rep(i,l+1,r+1) d[i]=d[i]-(m-N);
			rep(i,l+1,r+1) if (d[i-1]>d[i]) {
				swap(d[i-1],d[i]);
			} else {
				if (d[i-1]==d[i]) return true;
				break;
			}
			if (d[r]==N) --r;
			off+=m-N;
			m=N;
		}
	}
}

void solve() {
	read(n);
	rep(i,0,n) read(a[i]);
	if (n==2) {
		println(a[0]+a[1]-gcd(a[0],a[1]));
		return;
	}
	L=a[1],R=a[0]+a[1]-gcd(a[0],a[1])+1;
	while (L+1<R) {
		ll md=(L+R)>>1;
		if (hascycle(md)) R=md; else L=md;
	}
	println(R-1);
}

int _;
int main() {
	for (read(_);_;_--) {
		solve();
	}
}

提出情報

コンパイルエラー

Main.cpp: In member function ‘void fastIO::Ostream_fwrite::print(int)’:
Main.cpp:138:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  138 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                         ^~
Main.cpp:138:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  138 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                                          ^~
Main.cpp: In member function ‘void fastIO::Ostream_fwrite::println(int)’:
Main.cpp:144:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  144 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                         ^~
Main.cpp:144:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  144 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                                          ^~
Main.cpp:146:25: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
  146 |                         while(s1--!=s)out(*s1); out('\n');
      |                         ^~~~~
Main.cpp:146:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
  146 |                         while(s1--!=s)out(*s1); out('\n');
      |                                                 ^~~
Main.cpp: In member function ‘void fastIO::Ostream_fwrite::print(long long int)’:
Main.cpp:150:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  150 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                         ^~
Main.cpp:150:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  150 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                                          ^~
Main.cpp: In member function ‘void fastIO::Ostream_fwrite::println(long long int)’:
Main.cpp:156:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  156 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                         ^~
Main.cpp:156:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  156 |                         if (!x)*s1++='0';if (x<0)out('-'),x=-x;
      |                                          ^~
Main.cpp:158:25: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
  158 |                         while(s1--!=s)out(*s1); out('\n');
      |                         ^~~~~
Main.cpp:158:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
  158 |                         while(s1--!=s)out(*s1); out('\n');
      |                                                 ^~~
Main.cpp: In member function ‘void fastIO::Ostream_fwrite::print(double, int)’:
Main.cpp:164:25: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  164 |                         if (x<-1e-12)out('-'),x=-x;x*=mul[y];
      |                         ^~
Main.cpp:164:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  164 |                         if (x<-1e-12)out('-'),x=-x;x*=mul[y];
      |                                                    ^
Main.cpp:167:61: warning: comparison of integer expressions of different signedness: ‘size_t’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  167 |                         if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];++i) out('0'); print(x3);}
      |                                                            ~^~

ジャッジ結果