Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:57:4827
2016-05-12 13:53:5127
2016-05-12 13:49:560
2016-05-12 13:44:4812
2016-05-12 13:35:590
2016-05-12 13:26:360
2016-05-12 13:12:380
2016-05-12 13:10:410
2016-05-12 13:04:140
2016-05-12 12:58:280
2016-05-12 12:57:190
2016-05-12 12:54:590
2016-05-12 12:54:24
2016-05-12 12:35:580
2016-05-12 12:35:050
2016-05-12 12:32:350
Task:Spiral
Sender:jDomantas
Submission time:2016-05-12 13:57:48
Language:C++
Status:READY
Score:27

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3WRONG ANSWER0
#4WRONG ANSWER0
#5WRONG ANSWER0

Test results

testverdicttime (s)group
#1ACCEPTED0.10 / 1.501details
#2ACCEPTED0.10 / 1.502details
#3WRONG ANSWER0.09 / 1.503details
#4WRONG ANSWER0.12 / 1.504details
#5WRONG ANSWER0.09 / 1.505details

Compiler report

input/code.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:20000000")
 ^

Code

#pragma comment(linker, "/stack:20000000")
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <limits.h>
#include <algorithm>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <fstream>
using namespace std;
/**/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pll, ll> plll;
typedef pair<double, double> pdd;

#define fst first
#define snd second

#define mp(a, b) make_pair((a), (b))
#define pp push_back
#define PI 3.1415926535897.9323846264338327

#define fori(n) for(int i = 0; i < (n); ++i)
#define forj(n) for(int j = 0; j < (n); ++j)
#define forir(n) for(int i = (n) - 1; i >= 0; --i)
#define forjr(n) for(int j = (n) - 1; j >= 0; --j)

void redirectIO() {
#if defined(_DEBUG) || defined(_RELEASE)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

#define mod (ll)((ll)1e9 + (ll)7)

#if defined(_DEBUG) || defined(_RELEASE)
#define maxn 2000
#else
#define maxn 2000
#endif

ll sums[2100][2100];

ll single(ll x, ll y) {
	ll d = max(abs(x), abs(y)) + 1;
	ll g = ((4 * d) % mod * d) % mod;
	g = (g + 11 * (mod - d)) % mod;
	g = (g + 8) % mod;
	if (x >= 0 && abs(x) > abs(y)) {
		return (g + y + mod) % mod;
	} 
	if (y >= 0 && abs(x) <= abs(y)) {
		g = (g + 2 * d - 2) % mod;
		return (g - x + mod) % mod;
	}
	if (x <= 0 && abs(x) > abs(y)) {
		g = (g + 2 * d - 2) % mod;
		g = (g + 2 * d - 2) % mod;
		return (g - y + mod) % mod;
	}
	g = (g + 2 * d - 2) % mod;
	g = (g + 2 * d - 2) % mod;
	g = (g + 2 * d - 2) % mod;
	return (g + x + mod) % mod;
}

void init() {
	fori(2100) forj(2100) sums[i][j] = 0;
	int x = 1050;
	int y = 1050;
	int val = 2;
	int s = 1;
	sums[x][y] = 1;
	while (x >= 5 && y >= 5 && x < 2095 && y < 2095) {
		fori(s) {
			x++;
			sums[x][y] = val++;
		}
		fori(s) {
			y++;
			sums[x][y] = val++;
		}
		s++;
		fori(s) {
			x--;
			sums[x][y] = val++;
		}
		fori(s) {
			y--;
			sums[x][y] = val++;
		}
		s++;
	}

	for (int x = 0; x < 2100; x++)
		for (int y = 0; y < 2100; y++) {
			ll a = x == 0 ? 0 : sums[x - 1][y];
			ll b = y == 0 ? 0 : sums[x][y - 1];
			ll c = (x == 0 || y == 0) ? 0 : sums[x - 1][y - 1];
			sums[x][y] = (sums[x][y] - c + a + b + mod * (ll)4) % mod;
		}
}

ll sum(int x, int y) {
	x += 1050;
	y += 1050;
	return sums[x][y];
}

void check() {
	for (int x = -990; x <= 990; x++)
		for (int y = -990; y <= 990; y++) {
			ll t = sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
			t = (t + 4 * mod) % mod;
			if (t != single(x, y)) {
				cout << x << " " << y << endl;
				cout << t << endl;
				cout << single(x, y) << endl;
				return;
			}
		}
}

ll gs(ll n) {
	ll r = (n * (n + 1)) % mod;
	r = (r * (((ll)2 * n + (ll)1) % mod)) % mod;
	r = ((((ll)2 * r) % mod) * (ll)333333336) % mod;

	ll a = ((n * (n + 1)) / 2) % mod;
	a = (11 * a) % mod;

	r = (r + mod - a) % mod;
	r = (r + (8 * n) % mod) % mod;

	return r;
}

ll gs2(ll n) {
	ll r = gs(n);
	r = (r + n * (n - 1)) % mod;
	return r;
}

// square (0; 0) (n; n)
ll psquare(ll n) {
	n++;

	ll r = (2 * n * n) % mod;
	r = (r * (n + 1)) % mod;
	r = (r * (n + 1)) % mod;

	ll a = (((4 * n) % mod) * (n + 1)) % mod;
	a = (a * ((2 * n + 1) % mod)) % mod;

	ll c = (12 * n * (n + 1)) % mod;
	ll d = (7 * n) % mod;

	r = (r + mod - a) % mod;
	r = (r + mod + c) % mod;
	r = (r + mod - d) % mod;

	return r;
}

// x >= y >= 0
ll prect1(ll x, ll y) {
	x++;
	y++;
	ll g = (gs(x) + mod - gs(y)) % mod;
	ll v = (y * (y - 1) / 2) % mod;
	g = ((g * y) % mod + v * (x - y) % mod) % mod;
	return (g + psquare(y - 1)) % mod;
}

//  y >= x >= 0
ll prect2(ll x, ll y) {
	x++;
	y++;
	ll g = (gs2(y) + mod - gs2(x)) % mod;
	ll v = (x * (x - 1) / 2) % mod;
	g = ((g * x) % mod + mod - v * (y - x) % mod) % mod;
	return (g + psquare(x - 1)) % mod;
}

// rectangle (0; 0) (x; y)
// x, y >= 0
ll prect(ll x, ll y) {
	if (x < 0 || y < 0) return 0;
	if (x >= y)
		return prect1(x, y);
	else
		return prect2(x, y);
}

ll p(ll x, ll y) {
	return (prect(x, y) - prect(x, 0) - prect(0, y) + 1 + 4 * mod) % mod;
}

int main()
{
	redirectIO();

	/*init();
	check();*/

	ll n, q;
	cin >> n >> q;
	//if (n > 1000) return 0;
	init();
	//check();
	int x1, y1, x2, y2;
	while (q--) {
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2 && y1 == y2 && n > 1000) {
			cout << single(x1, y1) << endl;
			continue;
		}
		if (x1 == 1 && y1 == 1 && n > 1000) {
			cout << p(x2, y2) << endl;
			continue;
		}
		if (n > 1000) return 0;
		ll a = sum(x2, y2);
		ll b = sum(x1 - 1, y2);
		ll c = sum(x2, y1 - 1);
		ll d = sum(x1 - 1, y1 - 1);
		if (a < 0 || b < 0 || c < 0 || d < 0 || a >= mod || b >= mod || c >= mod || d >= mod)
			return 1;
		ll res = a - b - c + d + (ll)2 * (ll)mod;
		if (res < 0)
			return 1;
		res %= mod;
		cout << res << endl;
	}

	/*for (int y = 7; y >= 0; y--) {
		for (int x = 0; x <= 7; x++) {
			ll c = single(x, y);// sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
			cout << ((c + 3 * mod) % mod) << "\t";
		}
		cout << endl;
	}*/

	return 0;
}

// Park (B)

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000 100
-709 0 1000 123
-621 -1000 -102 -435
-602 -560 276 -356
-945 -590 0 -468
-106 -809 235 -277
-654 -317 975 1
42 -250 271 80
-537 -341 307 685
-939 -1000 67 429
-737 -743 -206 -656
-244 -816 210 -265
-948 -306 -693 149
1000 -230 1000 266
-1 146 497 780
1 -653 295 536
-629 413 235 505
-1000 -163 -1000 -127
-33 -773 128 29
-895 0 324 648
...
view   save

correct output
788057008
633127082
507903329
53165899
558016315
302089138
566211035
559423498
252507519
337514610
408751067
11314517
986518436
749615506
770971645
659417332
148042402
377036107
695769426
139996789
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
302089138
566211035
559423498
252507519
337514610
408751067
11314517
986518436
749615506
770971645
659417332
148042402
377036107
695769426
139996789
...
view   save

Test 2

Group: 2

Verdict: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
852751643 863389570 852751643 ...
-161213342 -447073611 -1612133...
813819781 -140986437 813819781...
-268931454 1 -268931454 1
-535129439 664254541 -53512943...
-37958808 536286414 -37958808 ...
570795830 -434946577 570795830...
405557765 652154349 405557765 ...
217542840 879737653 217542840 ...
-8797270 0 -8797270 0
263406926 -103702080 263406926...
417673370 -1 417673370 -1
-618520914 -724183720 -6185209...
-845795672 376533093 -84579567...
325062284 1 325062284 1
598762221 -430223124 598762221...
240779920 -225435228 240779920...
540964704 -76817080 540964704 ...
...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
472803047
812702745
911600992
712194929
656239841
844441902
822425230
890978307
121806251
534620131
983366131
922448146
929751481
1520635
549597234
...
view   save

user output
818946492
750635163
193830026
660632411
46072376
472803047
812702745
911600992
712194929
656239841
844441902
822425230
890978307
121806251
534620131
983366131
922448146
929751481
1520635
549597234
...
view   save

Test 3

Group: 3

Verdict: WRONG ANSWER

input
100000 100
-88233 -87279 -49871 52277
-86645 -7997 48948 30702
-79916 -36210 -21257 -16821
0 57331 93163 100000
44248 -92086 82069 33876
-94630 25007 -25590 98962
16155 -5755 96544 62759
-81488 -26648 23 100000
-14958 56727 93378 89262
8115 -61830 100000 14245
81406 -71848 89340 -27273
-21732 -3446 0 90611
-29732 -31333 -17581 88824
-49910 -100000 75765 60308
-99934 99821 -2437 100000
-30488 3497 27202 85753
-96429 -60310 94121 -52638
-91077 -72776 -55352 0
-60349 -93167 -22305 -70442
...
view   save

correct output
986592951
708386765
85336595
18263594
32233727
191927838
917012013
68207304
680109056
161693316
718423685
402706528
445400315
482305558
902547162
575661103
458292319
248089294
568361776
369103934
...
view   save

user output
(empty)
view   save

Test 4

Group: 4

Verdict: WRONG ANSWER

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
1 1 1 343367274
1 1 124752051 466376574
1 1 881274458 333485384
1 1 1 639843287
1 1 218885316 41069224
1 1 389032543 1
1 1 559995242 339166021
1 1 1000000000 1
1 1 576960949 906365100
1 1 1 665174609
1 1 479125748 1
1 1 863672278 963679556
1 1 167501216 1000000000
1 1 601316864 722654796
1 1 739729791 880627974
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
406010456
146562569
456690551
167395515
484286023
395206507
999999566
822116832
848601421
771498811
187752764
103974960
284245539
174771858
698363351
...
view   save

user output
695961158
375016168
137575768
522232140
58884045
406010456
146562569
456690551
167395515
484286023
395206507
999999566
822116832
848601421
771498811
187752764
103974960
284245539
174771858
698363351
...
view   save

Test 5

Group: 5

Verdict: WRONG ANSWER

input
1000000000 100
-857489445 -1000000000 -432836...
81977033 -740250254 605214029 ...
681633641 -1 786755036 1367416...
613219620 -629478605 763915005...
2964572 244317647 601041223 99...
-196156852 -128320437 69180975...
-542221994 -159095881 -2993968...
-297670401 305316465 207760864...
-647927334 -75065196 -1 301899...
-740735184 -979789736 1 -81317...
-893563915 -937860292 -7315639...
-150493935 -53307647 408566258...
4971883 120690836 643069370 70...
-899606935 -162385187 44595688...
74629300 517384780 458554953 6...
-1 417955698 802239354 7895247...
-860356476 -1000000000 -317982...
-807742787 -100142044 91420967...
-641658816 1142760 -29777797 7...
...
view   save

correct output
902627632
581519884
819269364
857298983
278402948
138389570
382251480
497385669
179802934
291456937
561433345
100042259
624201364
527261545
383179762
427359341
385615799
741162504
982984746
422953981
...
view   save

user output
(empty)
view   save