Submission #3045576
Source Code Expand
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
bool cmp_P(const P &a,const P &b){
return a.second < b.second;
}
int main()
{
int K,ma=2,mi=2,nm=2;
cin >> K;
vector<int> A(K,0);
REP(i,K)cin >> A[i];
if(A[K-1] != 2){
cout << "-1" << endl;
return 0;
}
for(int i=K-2;i>=0;i--){
int oa=ma,oi=mi;
while(1){
if(ma >= A[i] && ma % A[i] == A[i] - 1)
break;
ma++;
}
if(mi > A[i]){
int tmp = mi;
mi = 0;
if(tmp % A[i] != 0)
mi = (A[i])*(1+tmp/A[i]);
else
mi = A[i]*(tmp/A[i]);
}else
mi = max(mi,A[i]);
if(oa < (A[i+1])*((A[i]*(mi/A[i]))/(A[i+1]))){
cout << "-1" << endl;
return 0;
}
}
cout << mi <<" "<< ma << endl;
return 0;
}
int par[MAX_N];
int ranks[MAX_N];
//n要素で初期化
void init(int n){
REP(i,n){
par[i] = i;
ranks[i] = 0;
}
}
//木の根を求める
int find(int x){
if(par[x] == x){
return x;
}else{
return par[x] = find(par[x]);
}
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y) return ;
if(ranks[x] < ranks[y]){
par[x] = y;
}else{
par[y] = x;
if(ranks[x] == ranks[y]) ranks[x]++;
}
}
bool same(int x, int y){
return find(x) == find(y);
}
ll bpow(ll a, ll n,ll mod){
int i = 0;
ll res=1;
while(n){
if(n & 1)
res = (res*a) % mod;
a = (a*a) % mod;
n >>= 1;
}
return res;
}
const int MOD = 1000000007;
mat mul(mat &A, mat &B){
mat C(A.size(),vec(B[0].size()));
REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
}
return C;
}
mat pow(mat A,ll n)
{
mat B(A.size(),vec(A.size()));
REP(i,A.size()){
B[i][i] = 1;
}
while(n > 0){
if ( n & 1) B = mul(B,A);
A = mul(A,A);
n >>= 1;
}
return B;
}
Submission Info
Submission Time |
|
Task |
B - Ice Rink Game |
User |
makss |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2519 Byte |
Status |
WA |
Exec Time |
2103 ms |
Memory |
640 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
WA |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
1 ms |
256 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
17 ms |
640 KB |
subtask_1_07.txt |
AC |
43 ms |
640 KB |
subtask_1_08.txt |
AC |
1 ms |
256 KB |
subtask_1_09.txt |
TLE |
2103 ms |
256 KB |
subtask_1_10.txt |
TLE |
2103 ms |
256 KB |
subtask_1_11.txt |
TLE |
2103 ms |
640 KB |
subtask_1_12.txt |
TLE |
2103 ms |
640 KB |
subtask_1_13.txt |
AC |
30 ms |
640 KB |
subtask_1_14.txt |
TLE |
2103 ms |
640 KB |
subtask_1_15.txt |
TLE |
2103 ms |
640 KB |
subtask_1_16.txt |
TLE |
2103 ms |
256 KB |
subtask_1_17.txt |
TLE |
2103 ms |
640 KB |
subtask_1_18.txt |
TLE |
2103 ms |
640 KB |
subtask_1_19.txt |
TLE |
2103 ms |
640 KB |
subtask_1_20.txt |
TLE |
2103 ms |
640 KB |
subtask_1_21.txt |
TLE |
2103 ms |
640 KB |
subtask_1_22.txt |
AC |
29 ms |
640 KB |
subtask_1_23.txt |
AC |
1564 ms |
256 KB |
subtask_1_24.txt |
TLE |
2103 ms |
256 KB |
subtask_1_25.txt |
TLE |
2103 ms |
640 KB |
subtask_1_26.txt |
TLE |
2103 ms |
256 KB |
subtask_1_27.txt |
TLE |
2103 ms |
640 KB |