結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-21 02:07:29 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,815 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 84,128 KB |
実行使用メモリ | 6,912 KB |
最終ジャッジ日時 | 2024-07-02 17:38:32 |
合計ジャッジ時間 | 3,696 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:62:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 62 | scanf("%d%lld%lld", &n, &l, &r); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:64:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | for (int i = 0; i < n; i++) scanf("%lld", as + i); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 911.cc: No.911 ラッキーソート - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 200000;const int BN = 61;/* typedef */typedef long long ll;/* global variables */ll as[MAX_N], es[MAX_N], dp[BN + 1];int ds[BN], bits[BN + 1];/* subroutines */ll count(ll a) {ll c = 0;for (int k = BN; k >= 0; k--) {if (((a >> k) & 1) == 0) {if (! (bits[k] & 1)) break;}else {if (bits[k] & 1) c += dp[k];if (! (bits[k] & 2)) break;}}return c;}/* main */int main() {int n;ll l, r;scanf("%d%lld%lld", &n, &l, &r);for (int i = 0; i < n; i++) scanf("%lld", as + i);bits[BN] = 3;for (int k = BN - 1; k >= 0; k--) {ll bk = 1LL << k;int ok0 = 1, ok1 = 1;ll pe0 = es[0] | (as[0] & bk), pe1 = pe0 ^ bk;for (int i = 1; i < n; i++) {ll ei0 = es[i] | (as[i] & bk), ei1 = ei0 ^ bk;if (pe0 > ei0) ok0 = 0;if (pe1 > ei1) ok1 = 0;pe0 = ei0, pe1 = ei1;}ds[k] = ok0 + ok1;bits[k] = ok0 | (ok1 << 1);if (ds[k] == 0) {puts("0");return 0;}ll xk = (ok0) ? 0 : bk;for (int i = 0; i < n; i++) es[i] |= ((as[i] & bk) ^ xk);}dp[0] = 1;for (int k = 0; k < BN; k++) dp[k + 1] = dp[k] * ds[k];//for (int i = 0; i < BN; i++) putchar('0' + ds[i]); putchar('\n');ll cl = count(l), cr = count(r + 1);// printf("cl=%lld, cr=%lld\n", cl, cr);printf("%lld\n", cr - cl);return 0;}