Submission #349416

#	Time	Username	Problem	Language	Result	Execution time	Memory
349416		S2speed	Spiral (BOI16_spiral)	C++17	15 / 100	1 ms	364 KiB

spiral

#include<bits/stdc++.h>
#include<fstream>
 
using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<int , pii> piii;

const ll MAXN = 1e5 + 20 , md = 1e9 + 7;
// check problem statement
// y "a0" first element
// y(y - 1) / 2 "t" first increse
// (y - 2)(y - 1)(2y - 3) / 12 + (y - 2)(y - 1) / 4 "z" increase of increase

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n;
			res %= md;
		}
		n *= n;
		n %= md;
		k /= 2;
	}
	return res;
}

unordered_map<ll , ll> mp;
ll a[MAXN][2][2] , in[MAXN][2][2];

ll f(ll a0 , ll t , ll z , ll y){
	ll h = 0 , q = 0 , o = 0;
	h = 1ll * y * a0;
	h %= md;
	q = 1ll * y * (y - 1);
	q %= md;
	q *= t;
	q %= md;
	q *= mp[2];
	q %= md;
	h += q;
	q = 1ll * (y - 2) * (y - 1);
	q %= md;
	q *= (2 * y - 3);
	q %= md;
	q *= mp[12];
	q %= md;
	o = q;
	q = 1ll * (y - 2) * (y - 1);
	q %= md;
	q *= mp[4];
	q %= md;
	o += q;
	o *= z;
	o %= md;
	h += o;
	h %= md;
	return h;
}

int main(){ // check MAXN
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	mp[2] = tav(2 , md - 2);
	mp[4] = tav(4 , md - 2);
	mp[12] = tav(12 , md - 2);
	ll n , q;
	cin>>n>>q;
//	if(n > MAXN){
		while(q--){
			ll x1 , x2 , y1 , y2;
			cin>>x1>>y1>>x2>>y2;
			if(x1 == 0 && y1 == 0){
				cout<<"1\n";
				continue;
			}
			ll q = max(abs(x1) , abs(y1)) , p = tav(2 * q - 1 , 2) + 1;
			if(x1 == q && y1 == -q){
				cout<<tav(2 * q + 1 , 2)<<'\n';
				continue;
			}
			if(x1 == q){
				cout<<(p + y1 + q - 1) % md<<'\n';
				continue;
			}
			p += 2 * q - 1;
			if(y1 == q){
				cout<<(p + q - x1) % md<<'\n';
				continue;
			}
			p += 2 * q;
			if(x1 == -q){
				cout<<(p + q - y1) % md<<'\n';
				continue;
			}
			p += 2 * q;
			cout<<(p + x1 + q) % md<<'\n';
		}
//	a[n][0][0] = 1;
	return 0;
}

/*

*/

• Subtask 1: 0 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25