結果
問題 | No.87 Advent Calendar Problem |
ユーザー |
|
提出日時 | 2018-01-12 19:05:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 310 ms / 5,000 ms |
コード長 | 3,064 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 167,672 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-24 00:37:32 |
合計ジャッジ時間 | 5,926 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define mt make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()#define pb push_backtypedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;bool isLeap(ll year) {return year % 400 == 0 || (year % 100 && year % 4 == 0);}int week[102];ll cnt[102];const int R = 100000000;int CNT[] = {0,14249713,28499713,42749713,56999713,71249713,85499713,99749713,113999713,128249713,142499713,156749713,170999713,185249713,199499713,213749713,227999713,242249713,256499713,270749713,284999713,299249713,313499713,327749713,341999713,356249713,370499713,384749713,398999713,413249713,427499713,441749713,455999713,470249713,484499713,498749713,512999713,527249713,541499713,555749713,569999713,584249713,598499713,612749713,626999713,641249713,655499713,669749713,683999713,698249713,712499713,726749713,740999713,755249713,769499713,783749713,797999713,812249713,826499713,840749713,854999713,869249713,883499713,897749713,911999713,926249713,940499713,954749713,968999713,983249713,997499713,1011749713,1025999713,1040249713,1054499713,1068749713,1082999713,1097249713,1111499713,1125749713,1139999713,1154249713,1168499713,1182749713,1196999713,1211249713,1225499713,1239749713,1253999713,1268249713,1282499713,1296749713,1310999713,1325249713,1339499713,1353749713,1367999713,1382249713,1396499713,1410749713,1424999713,};int WEEK[] = {0,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,0,};ll f(ll l, ll r, int x) {ll res = 0;for (ll i = l; i < r; ++i) {if (i > l) {if (isLeap(i))x += 2;else x += 1;if (x >= 7)x -= 7;}if (!x)res++;if (i%R == 0) {cnt[i/R] = res;}if (i%R == 1) {week[i / R] = x;}}return res;}void preCalc() {f(2014, 10000000001ll, 0);rep(i, 101) {cout << cnt[i] << "," << endl;}rep(i, 101) {cout << week[i] << "," << endl;}}int main(){ios::sync_with_stdio(false);cin.tie(0);//preCalc();// return 0;ll N;cin >> N;if (N<R) {cout << f(2014, N + 1, 0) - 1 << endl;} else {ll y = N / R*R;int x = WEEK[y / R];ll ans = CNT[y / R];ans += f(y + 1, N + 1, x) - 1;cout << ans << endl;}}