Submission #239603

#	Time	Username	Problem	Language	Result	Execution time	Memory
239603		maximath_1	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	146 ms	130552 KiB

skyscraper

/*
 ,          .      
-+-__. _.._ |_     
 |  /_(_][_)[ )____
         |              
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pqgreater(x) x, vector<x>, greater<x>
#define decimal(x) cout<<fixed<<setprecision(x)
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#define printtime cerr<<"\nTime elapsed: "<<1000*clock()/CLOCK_PER_SEC<<"ms\n";
#define sq(x) x*x
#define gc getchar//_unlocked
#define pc putchar//_unlocked
const int mod=1e9+7; //1e9+7 or 998244353, remove const if changing mods
const ld eps=1e-6;
const ld pi=3.1415926535897932384626433832795l;
const int dx4[]={-1, 0, 1, 0};
const int dy4[]={0, 1, 0, -1};
const int dx8[]={-1, 0, 1, 0, -1, -1, 1, 1};
const int dy8[]={0, 1, 0, -1, -1, 1, -1, 1};
const int dxhorse[]={-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[]={1, -1, 2, -2, 2, -2, 1, -1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ld sign(ld x){return (x>0)-(x<0);}
ll sign(ll x){return (x>0)-(x<0);}
int sign(int x){return (x>0)-(x<0);}
struct pt{
	ld x, y;
	pt(){}
	pt(ld _x, ld _y):x(_x), y(_y){}
	bool operator<(pt p){return tie(x, y)<tie(p.x, p.y);}
	bool operator==(pt p){return tie(x, y)==tie(p.x, p.y);}
	pt operator+(pt p){return {x+p.x, y+p.y};}
	pt operator-(pt p){return {x-p.x, y-p.y};}
	pt operator*(ld d){return {x*d, y*d};}
	pt operator/(ld d){return {x/d, y/d};}
	ld dot(pt p){return x*p.x+y*p.y;}
	ld det(pt p){return x*p.y-y*p.x;}
	ld cross(pt p, pt q){return (p-*this).det(q-*this);}
	ld dist(){return sqrtl(sq(x)+sq(y));}
	pt rot90(){return pt(-y, x);}
	pt unit(){return *this/dist();}
	ld angle(){return atan2(y, x);}
	pt rot(ld an){return {x*cos(an)-y*sin(an), x*sin(an)+y*cos(an)};}
	void read(){cin>>x>>y;}
	void write(){cout<<"("<<x<<","<<y<<")"<<endl;}
};

struct seg{
	pt fi, sc;
	seg(){}
	seg(pt _fi, pt _sc):fi(_fi), sc(_sc){}
	ld dist(pt C){
		if(fi==sc) return (C-fi).dist();
		ld d=pow((sc-fi).dist(), 2);
		ld t=min(d, max((ld)0.0, (C-fi).dot(sc-fi)));
		return ((C-fi)*d-(sc-fi)*t).dist()/d;
	}
	ld len(){return (fi-sc).dist();}
	bool on_seg(pt C){
		return abs(C.cross(fi, sc))<eps && (fi-C).dot(sc-C)<=eps;
	}
	vector<pt>intersect(seg rhs){
		ld oa=rhs.fi.cross(rhs.sc, fi);
		ld ob=rhs.fi.cross(rhs.sc, sc);
		ld oc=fi.cross(sc, rhs.fi);
		ld od=fi.cross(sc, rhs.sc);
		if(sign(oa)*sign(ob)<0 && sign(oc)*sign(od)<0)
			return {(fi*ob-sc*oa)/(ob-oa)};
		vector<pt>ans;
		if(rhs.on_seg(fi)) ans.push_back(fi);
		if(rhs.on_seg(sc)) ans.push_back(sc);
		if(on_seg(rhs.fi)) ans.push_back(rhs.fi);
		if(on_seg(rhs.sc)) ans.push_back(rhs.sc);
		return ans;
	}
};

struct line{
	ld a, b, c; //line a*x+b*y=c
	line(pt p1, pt p2){
		assert(!(p1==p2));
		a=p2.y-p1.y;
		b=p1.x-p2.x;
		c=a*p1.x+b*p1.y;
	}
	line(){}
	line(ld _a, ld _b, ld _c):a(_a), b(_b), c(_c){}
	ld dist(pt p){
		return fabs(a*p.x+b*p.y-c)/sqrtl(a*a+b*b);
	}
	pair<int, pt>intersect(line rhs){
		ld dett=a*rhs.b-b*rhs.a;
		if(fabs(dett)<=eps){
			ld det2=c*rhs.a-a*rhs.c;
			if(fabs(det2)<=eps)
				return {-1, pt()}; //infinte
			return {0, pt()}; //no sol
		}
		return {1, pt((c*rhs.b-rhs.c*b)/dett, (a*rhs.c-c*rhs.a)/dett)};
	}
};

pt reflect(pt A, line L){
	line perpendicular(-L.b, L.a, -L.b*A.x+L.a*A.y);
	pt insect=perpendicular.intersect(L).second;
	return insect*(ld)2.0-A;
}

struct mint{
	int val;
	mint(){val=0;}
	mint(const ll& v){
		val=(-mod<=v && v<mod)?v:v%mod;
		if(val<0) val+=mod;
	}
	friend ostream& operator<<(ostream&os, const mint&a){return os<<a.val;}
	friend bool operator==(const mint&a, const mint&b){return a.val==b.val;}
	friend bool operator!=(const mint&a, const mint&b){return a.val!=b.val;}
	friend bool operator<(const mint&a, const mint&b){return a.val<b.val;}
	friend bool operator>(const mint&a, const mint&b){return a.val>b.val;}
	friend bool operator<=(const mint&a, const mint&b){return a.val<=b.val;}
	friend bool operator>=(const mint&a, const mint&b){return a.val>=b.val;}

	mint operator-(){return mint(-val);}
	mint& operator+=(const mint&m){if((val+=m.val)>=mod) val-=mod; return *this;}
	mint& operator-=(const mint&m){if((val-=m.val)<0) val+=mod; return *this;}
	mint& operator*=(const mint&m){val=(val*1ll*m.val)%mod; return *this;}
	friend mint pow(mint a, int p){
		mint ans=mint(1);
		for(; p; p/=2, a*=a)
			if(p%2==1) ans*=a;
		return ans;
	}
	friend mint inv(const mint&a){return pow(a, mod-2);}
	mint& operator/=(const mint&m){return (*this)*=inv(m);}
	friend mint operator+(mint a, const mint&b){return a+=b;}
	friend mint operator-(mint a, const mint&b){return a-=b;}
	friend mint operator*(mint a, const mint&b){return a*=b;}
	friend mint operator/(mint a, const mint&b){return a/=b;}
};

pair<int, int> extendedEuclid(int a, int b){
	if(a==0){return {0, 1};}
	pair<int, int>get=extendedEuclid(b%a, a);
	pair<int, int>ans;
	ans.first=get.second-(b/a)*get.first;
	ans.second=get.first;
	return ans;
}

int get(){
	char c;
	for(c=gc(); c<'0' || '9'<c; c=gc());
	int nw=c-'0';
	for(c=gc(); '0'<=c && c<='9'; c=gc())
		nw=(nw<<3)+(nw<<1)+c-'0';
	return nw;
}
char number[22];
void put(int nw){
	int id=0;
	for(; nw; nw/=10) number[id++]=nw%10+'0';
	for(int i=id-1; i>=0; i--) pc(number[i]);
}

/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////

int solve(); void precomp();
#define multitest 0
#define usecase 0
#define usedecimal 0
int main(){ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t=1;
	if(multitest) cin>>t;
	if(usedecimal) decimal(10);
	precomp();
	for(int tc=1; tc<=t; tc++){
		if(multitest && usecase)
			cout<<"Case #"<<tc<<": ";
		solve();
	}
}

mint dp[105][105][1005][3];
void precomp(){
	for(int i=0; i<105; i++) for(int j=0; j<105; j++)
		for(int k=0; k<1005; k++) for(int m=0; m<3; m++)
			dp[i][j][k][m]=mint(0);
	return;
}

//idx, n_cc, sum, endpoints
int n, l, a[105];
int solve(){
	scanf("%d%d", &n, &l);
	for(int i=0; i<n; i++) scanf("%d", &a[i]);
	sort(a, a+n);
	if(n==1){printf("1\n"); return 0;}
	a[n]=100000;
	if(a[1]-a[0]<=l)
		dp[1][1][a[1]-a[0]][1]=2; //put at edge
	if(2*(a[1]-a[0])<=l)
		dp[1][1][2*(a[1]-a[0])][0]=1; //put at mid
	for(int i=1; i<n; i++){
		int dif=a[i+1]-a[i];
		for(int j=1; j<=i; j++) for(int k=0; k<=l; k++) for(int m=0; m<3; m++){
			if(dp[i][j][k][m]==mint(0)) continue;
			//put at end
			if(m<2 && k+dif*(2*j-m-1)<=l){
				if(i==n-1)
					dp[i+1][j][k+dif*(2*j-m-1)][m+1]+=dp[i][j][k][m]*mint(2-m)*mint(j);
				else if(m==0 || j>1)
					dp[i+1][j][k+dif*(2*j-m-1)][m+1]+=dp[i][j][k][m]*mint(2-m)*mint(j-m); //add with cc bf end
				if(k+dif*(2*j-m+1)<=l)
					dp[i+1][j+1][k+dif*(2*j-m+1)][m+1]+=dp[i][j][k][m]*mint(2-m); //create at end
			}
			//create new
			if(k+dif*(2*j-m+2)<=l)
				dp[i+1][j+1][k+dif*(2*j-m+2)][m]+=dp[i][j][k][m];
			//stick one
			if(k+dif*(2*j-m)<=l)
				dp[i+1][j][k+dif*(2*j-m)][m]+=dp[i][j][k][m]*mint(2*j-m);
			//merge 2 cc
			if(k+dif*(2*j-m-2)<=l && j>=2 && !(i!=n-1 && j==2 && m==2)){
				if(m==0)
					dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j)*mint(j-1);
				if(m==1)
					dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j-1)*mint(j-1);
				if(m==2)
					if(i==n-1)
						dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m];
					else
						dp[i+1][j-1][k+dif*(2*j-m-2)][m]+=dp[i][j][k][m]*mint(j-2)*mint(j-1);
			}
		}
	}
	mint ans=mint(0);
	for(int i=0; i<=l; i++)
		ans+=dp[n][1][i][2];
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int solve()':
skyscraper.cpp:241:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if(m==2)
       ^
skyscraper.cpp:207:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &l);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:208:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d", &a[i]);
                         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80