#362618 (C++14) No.854 公平なりんご分配

提出ソース

結果

問題	No.854 公平なりんご分配
ユーザー	👑 kmjp
提出日時	2019-07-26 22:11:32
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	472 ms / 3,153 ms
コード長	1,573 bytes
コンパイル時間	1,570 ms
コンパイル使用メモリ	168,992 KB
実行使用メモリ	124,480 KB
最終ジャッジ日時	2023-09-15 01:51:07
合計ジャッジ時間	12,759 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	2 ms 4,380 KB
testcase_16	AC	2 ms 4,380 KB
testcase_17	AC	2 ms 4,384 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	2 ms 4,380 KB
testcase_20	AC	2 ms 4,380 KB
testcase_21	AC	2 ms 4,380 KB
testcase_22	AC	4 ms 4,376 KB
testcase_23	AC	4 ms 4,380 KB
testcase_24	AC	6 ms 4,484 KB
testcase_25	AC	3 ms 4,384 KB
testcase_26	AC	6 ms 4,536 KB
testcase_27	AC	5 ms 4,616 KB
testcase_28	AC	4 ms 4,380 KB
testcase_29	AC	2 ms 4,380 KB
testcase_30	AC	3 ms 4,376 KB
testcase_31	AC	5 ms 4,404 KB
testcase_32	AC	41 ms 29,720 KB
testcase_33	AC	53 ms 17,332 KB
testcase_34	AC	89 ms 40,108 KB
testcase_35	AC	61 ms 31,752 KB
testcase_36	AC	47 ms 5,292 KB
testcase_37	AC	40 ms 27,788 KB
testcase_38	AC	32 ms 23,804 KB
testcase_39	AC	141 ms 42,036 KB
testcase_40	AC	60 ms 15,432 KB
testcase_41	AC	64 ms 25,672 KB
testcase_42	AC	78 ms 37,944 KB
testcase_43	AC	101 ms 27,604 KB
testcase_44	AC	102 ms 35,852 KB
testcase_45	AC	108 ms 11,232 KB
testcase_46	AC	134 ms 35,820 KB
testcase_47	AC	48 ms 21,756 KB
testcase_48	AC	69 ms 38,188 KB
testcase_49	AC	65 ms 38,004 KB
testcase_50	AC	36 ms 27,664 KB
testcase_51	AC	132 ms 37,924 KB
testcase_52	AC	93 ms 19,380 KB
testcase_53	AC	47 ms 19,440 KB
testcase_54	AC	89 ms 21,444 KB
testcase_55	AC	31 ms 19,536 KB
testcase_56	AC	28 ms 19,452 KB
testcase_57	AC	48 ms 17,384 KB
testcase_58	AC	96 ms 9,172 KB
testcase_59	AC	24 ms 15,592 KB
testcase_60	AC	62 ms 17,500 KB
testcase_61	AC	33 ms 7,320 KB
testcase_62	AC	74 ms 15,280 KB
testcase_63	AC	55 ms 15,308 KB
testcase_64	AC	22 ms 9,180 KB
testcase_65	AC	52 ms 33,800 KB
testcase_66	AC	44 ms 11,252 KB
testcase_67	AC	71 ms 23,520 KB
testcase_68	AC	76 ms 13,392 KB
testcase_69	AC	48 ms 42,036 KB
testcase_70	AC	27 ms 15,456 KB
testcase_71	AC	32 ms 17,408 KB
testcase_72	AC	63 ms 7,104 KB
testcase_73	AC	42 ms 27,640 KB
testcase_74	AC	88 ms 33,772 KB
testcase_75	AC	49 ms 17,484 KB
testcase_76	AC	69 ms 27,672 KB
testcase_77	AC	73 ms 37,880 KB
testcase_78	AC	98 ms 13,220 KB
testcase_79	AC	88 ms 23,580 KB
testcase_80	AC	81 ms 25,576 KB
testcase_81	AC	59 ms 25,584 KB
testcase_82	AC	289 ms 124,180 KB
testcase_83	AC	438 ms 124,204 KB
testcase_84	AC	438 ms 124,292 KB
testcase_85	AC	467 ms 124,460 KB
testcase_86	AC	206 ms 124,348 KB
testcase_87	AC	290 ms 124,344 KB
testcase_88	AC	286 ms 124,236 KB
testcase_89	AC	286 ms 124,480 KB
testcase_90	AC	291 ms 124,348 KB
testcase_91	AC	289 ms 124,176 KB
testcase_92	AC	472 ms 124,256 KB
testcase_93	AC	466 ms 124,300 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[101010];
int S[101010][305],Z[101010];
int Q,P,L,R;

const int prime_max = 2000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	cin>>N;
	FOR(i,N) {
		cin>>x;
		FOR(j,NP) {
			S[i+1][j]=S[i][j];
			if(x) {
				while(x%prime[j]==0) {
					S[i+1][j]++;
					x/=prime[j];
				}
			}
		}
		Z[i+1]=Z[i];
		if(x==0) Z[i+1]++;
	}
	cin>>Q;
	while(Q--) {
		cin>>P>>L>>R;
		L--;
		
		if(Z[R]-Z[L]) {
			cout<<"Yes"<<endl;
			continue;
		}
		
		FOR(i,NP) {
			x=0;
			while(P%prime[i]==0) {
				P/=prime[i];
				x++;
			}
			if(S[R][i]-S[L][i]<x) break;
		}
		if(i!=NP || P!=1) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
		}
		
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

yukicoder

結果

テストケース

ソースコード