QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #23915 | #1832. Crab's Cannon | ezoilearner | ML | 3ms | 3776kb | C++14 | 2.3kb | 2022-03-20 19:53:54 | 2022-04-30 04:25:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define cout cerr
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> pii;
#define FR first
#define SE second
inline void rd(int &x){
x=0;char ch=getchar();int f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
inline void rd(ll &x){
x=0;char ch=getchar();int f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
typedef pair<ll,ll> P;
typedef vector<P> H;
#define rez resize
int n;ll l;
#define Maxn 300010
ll a[Maxn];
ll gcd(ll a,ll b){
if(!b)return a;
return gcd(b,a%b);
}
H add(H ans,P cur){
int t=ans.size()-1;
if(ans[t].SE+cur.SE<=ans[t].FR){
ll tmp=gcd(ans[t].SE,cur.SE);
ans.pop_back();ans=add(ans,P(cur.FR,tmp));
return ans;
}
if(ans[t].SE>=cur.SE){
ll len=ans[t].FR-ans[t-1].FR;
len%=cur.SE;ans.pop_back();
if(len)ans=add(ans,P(ans[t-1].FR+len,len));
ans=add(ans,P(cur.FR,cur.SE));
return ans;
}else{
ll at=ans[t].FR-cur.SE;
if(at<0){
ans.push_back(cur);return ans;
}
bool fl=false;
if(at==0)fl=true;
else{
per(i,t,1)
if(at>ans[i-1].FR){
if((at-ans[i-1].FR)%ans[i].SE==0){
fl=true;
break;
}
}else{
H res;res.rez(i);rep(j,0,i-1)res[j]=ans[j];
ll hh=ans[i].SE;
if(at-ans[i-1].FR>hh)res=add(res,P(at/hh*hh,hh));
res=add(res,P(at,at%hh));
res=add(res,P((at-1)/hh*hh+hh,hh-at%hh));
if(at+hh<ans[i].FR)res=add(res,P(ans[i].FR,hh));
rep(j,i+1,t)res=add(res,ans[j]);
res=add(res,cur);
return res;
}
}
if(fl){
if(cur.SE%ans[t].SE==0)cur.SE=ans[t].SE;
ans.push_back(cur);
return ans;
}
}
}
int main(){
while(true){
rd(n);rd(l);
if(n==0&&l==0)break;
rep(i,1,n)rd(a[i]);a[++n]=1;
sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;
H ans;
ans.rez(2);ans[0]=P(0,0);ans[1]=P(1,1);
rep(i,2,n){
ans=add(ans,P(a[i],a[i]-a[i-1]));
}
ll Ans=0;
for(int i=1;i<ans.size();++i)Ans+=(ans[i].FR-ans[i-1].FR)/ans[i].SE;
printf("%lld\n",Ans);
}
return 0;
}/*
4 12
7 1 3 9
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3728kb
input:
3 7 1 3 7 4 12 7 1 3 9 3 16 16 1 8 0 0
output:
3 5 3
result:
ok 3 number(s): "3 5 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
2 1048576 1 1048576 2 1048576 1048576 1 2 1048576 51135 13546 2 1048576 13546 51135 2 1048576 1 51135 2 1048576 51135 1 1 1048576 1 1 1048576 1048576 1 1048576 51135 2 104857600000000000 1 104857600000000000 2 104857600000000000 104857600000000000 1 2 104857600000000000 5113500000000 13546 2 1048576...
output:
2 2 3 3 2 2 1 2 2 2 2 3 3 2 2 1 2 2 2 3 3
result:
ok 21 numbers
Test #3:
score: -100
Memory Limit Exceeded
input:
5 96 7 12 61 37 93 4 100 63 2 16 35 5 88 7 43 70 23 8 4 29 22 7 5 14 1 2 2 2 3 2 3 0 0