Submission #1025757
Source Code Expand
#include <algorithm> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i)) #define rep(i,n) FOR(i,0,n) #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second #define all(v) begin(v), end(v) #define debug(x) cerr<< #x <<": "<<x<<endl #define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef vector<vector<ll> > vvll; template<class T> using vv=vector<vector< T > >; int mod = 1e9 + 7; int main() { ll l; scanf("%lld", &l); if (l <= 8) { printf("0\n"); return 0; } ll ans = 0; ans += (l/3 - 2) % mod; // x, x+1, x+2, l >= 9 ans %= mod; if (l <= 10) { printf("%lld\n", ans); return 0; } ll b3 = (l+1)/3; ll b3mod = b3 % mod; //debug(b3); //debug(((b3mod*(b3mod+1)/2) % mod + 3 + 3 * (mod - b3mod)) % mod); ans += ((b3mod*(b3mod+1)/2) % mod + 3 + 3 * (mod - b3mod)) % mod; ans %= mod; ll b4 = (l-3)/2; ll b4mod = b4 % mod; //debug(b4); //debug(((l-2)*(b4-b3) % mod + b3mod*(b3mod+1) % mod + (mod - (b4mod*(b4mod+1) % mod))) % mod); ans += (((l-2)%mod)*((b4-b3)%mod) % mod + b3mod*(b3mod+1) % mod + (mod - (b4mod*(b4mod+1) % mod))) % mod; ans %= mod; if (l <= 12) { printf("%lld\n", ans); return 0; } ll b1 = (l-1)/4; ll b1mod = b1 % mod; //debug(b1); //debug((b1mod*(b1mod+1)/2 + 1 + 2*(mod - b1mod)) % mod); ans += ((b1mod*(b1mod+1)/2) % mod + 1 + 2*(mod - b1mod)) % mod; ans %= mod; ll b2 = (l-4)/3; ll b2mod = b2 % mod; //debug(b2); //debug(((l-3)*(b2-b1) + b1mod*(b1mod+1)/2*3 + mod - (((b2mod*(b2mod+1))/2*3) % mod)) % mod); ans += (((l-3)%mod)*((b2-b1)%mod) % mod + (b1mod*(b1mod+1)/2*3) % mod + mod - (((b2mod*(b2mod+1))/2*3) % mod)) % mod; ans %= mod; printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 擬二等辺三角形 |
User | tspcx |
Language | C++14 (Clang++ 3.4) |
Score | 100 |
Code Size | 2349 Byte |
Status | AC |
Exec Time | 24 ms |
Memory | 1216 KB |
Judge Result
Set Name | small | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 25 / 25 | 75 / 75 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
small | 00_sample_1.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 20_subtask_00.txt, 20_subtask_01.txt, 20_subtask_02.txt, 20_subtask_03.txt, 20_subtask_04.txt, 20_subtask_05.txt, 20_subtask_06.txt, 20_subtask_07.txt, 20_subtask_08.txt, 20_subtask_09.txt, 20_subtask_10.txt, 20_subtask_11.txt, 20_subtask_12.txt, 20_subtask_13.txt, 20_subtask_14.txt, 20_subtask_15.txt, 20_subtask_16.txt, 20_subtask_17.txt, 20_subtask_18.txt, 20_subtask_19.txt, 20_subtask_20.txt, 20_subtask_21.txt, 20_subtask_22.txt, 20_subtask_23.txt, 20_subtask_24.txt, 20_subtask_25.txt, 20_subtask_26.txt, 20_subtask_27.txt, 20_subtask_28.txt, 20_subtask_29.txt, 20_subtask_30.txt, 20_subtask_31.txt, 20_subtask_32.txt, 20_subtask_33.txt, 20_subtask_34.txt, 20_subtask_35.txt, 20_subtask_36.txt, 20_subtask_37.txt, 20_subtask_38.txt, 20_subtask_39.txt |
All | 00_sample_1.txt, 10_small_00.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 10_small_11.txt, 10_small_12.txt, 10_small_13.txt, 10_small_14.txt, 10_small_15.txt, 10_small_16.txt, 10_small_17.txt, 10_small_18.txt, 10_small_19.txt, 20_subtask_00.txt, 20_subtask_01.txt, 20_subtask_02.txt, 20_subtask_03.txt, 20_subtask_04.txt, 20_subtask_05.txt, 20_subtask_06.txt, 20_subtask_07.txt, 20_subtask_08.txt, 20_subtask_09.txt, 20_subtask_10.txt, 20_subtask_11.txt, 20_subtask_12.txt, 20_subtask_13.txt, 20_subtask_14.txt, 20_subtask_15.txt, 20_subtask_16.txt, 20_subtask_17.txt, 20_subtask_18.txt, 20_subtask_19.txt, 20_subtask_20.txt, 20_subtask_21.txt, 20_subtask_22.txt, 20_subtask_23.txt, 20_subtask_24.txt, 20_subtask_25.txt, 20_subtask_26.txt, 20_subtask_27.txt, 20_subtask_28.txt, 20_subtask_29.txt, 20_subtask_30.txt, 20_subtask_31.txt, 20_subtask_32.txt, 20_subtask_33.txt, 20_subtask_34.txt, 20_subtask_35.txt, 20_subtask_36.txt, 20_subtask_37.txt, 20_subtask_38.txt, 20_subtask_39.txt, 30_large_00.txt, 30_large_01.txt, 30_large_02.txt, 30_large_03.txt, 30_large_04.txt, 30_large_05.txt, 30_large_06.txt, 30_large_07.txt, 30_large_08.txt, 30_large_09.txt, 30_large_10.txt, 30_large_11.txt, 30_large_12.txt, 30_large_13.txt, 30_large_14.txt, 30_large_15.txt, 30_large_16.txt, 30_large_17.txt, 30_large_18.txt, 30_large_19.txt, 50_maximum_1.txt, 80_sample_2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_1.txt | AC | 24 ms | 996 KB |
10_small_00.txt | AC | 22 ms | 1132 KB |
10_small_01.txt | AC | 23 ms | 1008 KB |
10_small_02.txt | AC | 23 ms | 1180 KB |
10_small_03.txt | AC | 21 ms | 1204 KB |
10_small_04.txt | AC | 22 ms | 1012 KB |
10_small_05.txt | AC | 22 ms | 1008 KB |
10_small_06.txt | AC | 23 ms | 1132 KB |
10_small_07.txt | AC | 23 ms | 1012 KB |
10_small_08.txt | AC | 23 ms | 1008 KB |
10_small_09.txt | AC | 22 ms | 1012 KB |
10_small_10.txt | AC | 22 ms | 1012 KB |
10_small_11.txt | AC | 23 ms | 1008 KB |
10_small_12.txt | AC | 23 ms | 1008 KB |
10_small_13.txt | AC | 22 ms | 1204 KB |
10_small_14.txt | AC | 21 ms | 1012 KB |
10_small_15.txt | AC | 22 ms | 1204 KB |
10_small_16.txt | AC | 20 ms | 1004 KB |
10_small_17.txt | AC | 23 ms | 976 KB |
10_small_18.txt | AC | 22 ms | 1012 KB |
10_small_19.txt | AC | 22 ms | 1008 KB |
20_subtask_00.txt | AC | 22 ms | 1136 KB |
20_subtask_01.txt | AC | 22 ms | 1012 KB |
20_subtask_02.txt | AC | 22 ms | 1008 KB |
20_subtask_03.txt | AC | 23 ms | 1132 KB |
20_subtask_04.txt | AC | 22 ms | 1008 KB |
20_subtask_05.txt | AC | 22 ms | 1008 KB |
20_subtask_06.txt | AC | 21 ms | 1132 KB |
20_subtask_07.txt | AC | 22 ms | 1004 KB |
20_subtask_08.txt | AC | 23 ms | 1072 KB |
20_subtask_09.txt | AC | 23 ms | 1132 KB |
20_subtask_10.txt | AC | 21 ms | 1008 KB |
20_subtask_11.txt | AC | 22 ms | 1140 KB |
20_subtask_12.txt | AC | 23 ms | 1012 KB |
20_subtask_13.txt | AC | 21 ms | 1012 KB |
20_subtask_14.txt | AC | 21 ms | 1132 KB |
20_subtask_15.txt | AC | 23 ms | 1008 KB |
20_subtask_16.txt | AC | 22 ms | 1132 KB |
20_subtask_17.txt | AC | 22 ms | 1012 KB |
20_subtask_18.txt | AC | 23 ms | 1012 KB |
20_subtask_19.txt | AC | 22 ms | 1012 KB |
20_subtask_20.txt | AC | 22 ms | 1212 KB |
20_subtask_21.txt | AC | 23 ms | 1012 KB |
20_subtask_22.txt | AC | 21 ms | 1008 KB |
20_subtask_23.txt | AC | 22 ms | 1136 KB |
20_subtask_24.txt | AC | 22 ms | 1132 KB |
20_subtask_25.txt | AC | 22 ms | 1084 KB |
20_subtask_26.txt | AC | 21 ms | 1216 KB |
20_subtask_27.txt | AC | 23 ms | 1012 KB |
20_subtask_28.txt | AC | 23 ms | 1012 KB |
20_subtask_29.txt | AC | 23 ms | 1012 KB |
20_subtask_30.txt | AC | 23 ms | 1004 KB |
20_subtask_31.txt | AC | 21 ms | 1012 KB |
20_subtask_32.txt | AC | 21 ms | 1004 KB |
20_subtask_33.txt | AC | 21 ms | 1012 KB |
20_subtask_34.txt | AC | 22 ms | 1004 KB |
20_subtask_35.txt | AC | 22 ms | 1004 KB |
20_subtask_36.txt | AC | 22 ms | 1008 KB |
20_subtask_37.txt | AC | 23 ms | 1136 KB |
20_subtask_38.txt | AC | 21 ms | 1008 KB |
20_subtask_39.txt | AC | 23 ms | 1080 KB |
30_large_00.txt | AC | 23 ms | 1132 KB |
30_large_01.txt | AC | 22 ms | 1020 KB |
30_large_02.txt | AC | 22 ms | 1008 KB |
30_large_03.txt | AC | 21 ms | 1012 KB |
30_large_04.txt | AC | 21 ms | 1008 KB |
30_large_05.txt | AC | 22 ms | 1000 KB |
30_large_06.txt | AC | 20 ms | 1008 KB |
30_large_07.txt | AC | 22 ms | 1000 KB |
30_large_08.txt | AC | 22 ms | 996 KB |
30_large_09.txt | AC | 22 ms | 1012 KB |
30_large_10.txt | AC | 22 ms | 1000 KB |
30_large_11.txt | AC | 20 ms | 1012 KB |
30_large_12.txt | AC | 22 ms | 1004 KB |
30_large_13.txt | AC | 22 ms | 1008 KB |
30_large_14.txt | AC | 23 ms | 1012 KB |
30_large_15.txt | AC | 22 ms | 1004 KB |
30_large_16.txt | AC | 22 ms | 1008 KB |
30_large_17.txt | AC | 22 ms | 1208 KB |
30_large_18.txt | AC | 22 ms | 1008 KB |
30_large_19.txt | AC | 22 ms | 1004 KB |
50_maximum_1.txt | AC | 22 ms | 1012 KB |
80_sample_2.txt | AC | 22 ms | 1004 KB |