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 11:31:3627
2016-05-12 11:27:3715
2016-05-12 11:23:300
Task:Spiral
Sender:perchema
Submission time:2016-05-12 11:31:36
Language:C++
Status:READY
Score:27

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3TIME LIMIT EXCEEDED0
#4TIME LIMIT EXCEEDED0
#5TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.81 / 1.501details
#2ACCEPTED0.06 / 1.502details
#3TIME LIMIT EXCEEDED-- / 1.503details
#4TIME LIMIT EXCEEDED-- / 1.504details
#5TIME LIMIT EXCEEDED-- / 1.505details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:62:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i", &n, &qCnt);
                           ^
input/code.cpp:66:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i %i", &x1, &y1, &x2, &y2);
                                           ^

Code

#include <bits/stdc++.h>

const int32_t MOD = 1e9 + 7;

int32_t n;

int32_t get_at_cell(int32_t x, int32_t y) {
	if ((x == n) && (y == n)) {
		return 1;
	}

	y = 2 * n - y;

	int64_t ringX = abs(n - x);
	int64_t ringY = abs(n - y);

	int64_t ring = std::max(ringX, ringY);
	int64_t pos;

	if (ringX > ringY) {
		if (x > n) {
			pos = (2 * n - y) - (n - ring);
		} else {
			pos = 4 * ring + y - (n - ring);
		}
	} else {
		if (y < n) {
			pos = 2 * ring + (2 * n - x) - (n - ring);
		} else {
			pos = 6 * ring + x - (n - ring);
		}
	}

	//printf("R%i P%i\n", ring, pos);

	/*int64_t sqrSide = (2 * ring - 1) % MOD;
	int64_t sqrCnt = sqrSide * sqrSide % MOD;
	int64_t sqrS = (sqrCnt * (sqrCnt - 1) / 2) % MOD;*/

	int64_t posSqr = (2 * ring - 1) * (2 * ring - 1) % MOD;
	//int64_t posSum = pos os + 1) / 2 % MOD + posSqr * pos;

	int64_t answ = (posSqr + pos) % MOD;
	if (answ < 0) {
		answ += MOD;
	}
	return answ;
}

int32_t sum_dumb(int32_t x1, int32_t y1, int32_t x2, int32_t y2) {
	int64_t sum = 0;
	for (int32_t x = x1;x <= x2;x++) {
		for (int32_t y = y1;y <= y2;y++) {
			sum = (sum + get_at_cell(x, y)) % MOD;
		}
	}
	return sum;
}

int main() {
	int32_t qCnt;
	scanf("%i %i", &n, &qCnt);

	for (int32_t i = 0;i < qCnt;i++) {
		int32_t x1, x2, y1, y2;
		scanf("%i %i %i %i", &x1, &y1, &x2, &y2);

		x1 += n;
		y1 += n;
		x2 += n;
		y2 += n;
		if ((x1 == x2) && (y1 == y2)) {
			printf("%i\n", get_at_cell(x1, y1));
		} else {
			printf("%i\n", sum_dumb(x1, y1, x2, y2));
		}
	}
}

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
...
view   save

correct output
788057008
633127082
507903329
53165899
558016315
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
...
view   save

Test 2

Group: 2

Verdict: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
...
view   save

user output
818946492
750635163
193830026
660632411
46072376
...
view   save

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 100
-88233 -87279 -49871 52277
-86645 -7997 48948 30702
-79916 -36210 -21257 -16821
0 57331 93163 100000
...
view   save

correct output
986592951
708386765
85336595
18263594
32233727
...
view   save

user output
(empty)

Test 4

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
...
view   save

user output
(empty)

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
1000000000 100
-857489445 -1000000000 -432836...
view   save

correct output
902627632
581519884
819269364
857298983
278402948
...
view   save

user output
(empty)