結果
問題 | No.979 Longest Divisor Sequence |
ユーザー | WarToks |
提出日時 | 2020-01-31 23:11:05 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 3,413 bytes |
コンパイル時間 | 1,213 ms |
コンパイル使用メモリ | 145,004 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-05-07 20:22:12 |
合計ジャッジ時間 | 2,200 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
12,800 KB |
testcase_01 | AC | 8 ms
12,800 KB |
testcase_02 | AC | 8 ms
12,928 KB |
testcase_03 | AC | 8 ms
12,928 KB |
testcase_04 | AC | 9 ms
12,928 KB |
testcase_05 | AC | 9 ms
12,928 KB |
testcase_06 | AC | 10 ms
13,056 KB |
testcase_07 | AC | 10 ms
12,800 KB |
testcase_08 | AC | 9 ms
12,928 KB |
testcase_09 | AC | 9 ms
13,056 KB |
testcase_10 | AC | 9 ms
13,056 KB |
testcase_11 | AC | 9 ms
12,928 KB |
testcase_12 | AC | 8 ms
13,184 KB |
testcase_13 | AC | 46 ms
15,172 KB |
testcase_14 | AC | 138 ms
19,968 KB |
testcase_15 | AC | 45 ms
16,000 KB |
ソースコード
#include <iostream> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cstring> #include <deque> #include <functional> #include <initializer_list> #include <math.h> #include <map> #include <random> #include <set> #include <stack> #include <tuple> #include <type_traits> #include <queue> #include <vector> #define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i)) #define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i)) #define REP(i, n) FOR(i, 0, n) #define rREP(i, n) rFOR(i, 0, (n-1)) #define SORT(A) std::sort((A).begin(), (A).end()) #define ALL(A) (A).begin(), (A).end() // 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A) #define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end()) using lli = long long int; using pii = std::pair<int, int>; // グリッド上の縦横移動 constexpr std::array<std::pair<int, int>, 4> dxdy = { std::pair<int, int>( 1, 0), std::pair<int, int>(-1, 0), std::pair<int, int>( 0, 1), std::pair<int, int>( 0, -1) }; void VintOut(std::vector<int>& A){ const int n = A.size(); if(n == 0){putchar('\n'); return;} printf("%d", A[0]); for(int i = 1; i < n; ++i) printf(" %d", A[i]); putchar('\n'); } void VintOut(std::vector<long long int>& A){ const int n = A.size(); if(n == 0){ putchar('\n'); return;} printf("%lld", A[0]); for(int i = 1; i < n; ++i) printf(" %lld", A[i]); putchar('\n'); } template <typename T> inline bool chmin(T& a, T b){ if(b < a){ a = b; return true;} return false; } template <typename T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false; } inline bool isIn(int x, int y, int H, int W){ return 0 <= x and x < H and 0 <= y and y < W; } inline bool bitUP(int state, int k){ return (state >> k) & 1; } inline bool bitUP(long long int state, int k){ return (state >> k) & 1;} // z-algorithm template <class T> std::vector<int> z_algorithm(const T &str) { const int n = str.size(); std::vector<int> resOfCP(n); resOfCP[0] = n; int i = 1, j = 0; while (i < n) { while (i + j < n and str[j] == str[i + j]) ++j; resOfCP[i] = j; if (j == 0) { ++i; continue;} int k = 1; while (i + k < n and k + resOfCP[k] < j) resOfCP[i + k] = resOfCP[k], ++k; i += k; j -= k; } return resOfCP; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ constexpr int MAX_N = 3e5 + 1; constexpr int MAX_A = 3e5 + 1; std::array<int, MAX_N> A; std::array<std::vector<int>, MAX_A> D; std::array<int, MAX_A> Len; std::array<int, MAX_A> Min; int main(void){ int n; scanf("%d", &n); for(int i = 0; i < n; ++i){ int a; scanf("%d", &a); D[a].push_back(i); A[i] = a; } for(int x = 1; x <= MAX_A; ++x) Min[x] = -1, Len[x] = (D[x].size() > 0) ? 1 : 0; int res = 0; for(int i = 0; i < n; ++i){ int j = A[i]; if(res < Len[j]) res = Len[j]; auto itr = std::upper_bound(D[j].begin(), D[j].end(), Min[j]); if(itr == D[j].end() or (*itr != i)) continue; for(int k = 2 * j; k <= MAX_A; k += j) if(D[k].size() > 0){ if(Len[k] < Len[j] + 1){ Len[k] = Len[j] + 1; Min[k] = i; } } } printf("%d\n", res); return 0; }