結果
問題 | No.2517 Right Triangles on Circle |
ユーザー | Astral__ |
提出日時 | 2023-10-27 21:33:30 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 314 ms / 2,000 ms |
コード長 | 6,771 bytes |
コンパイル時間 | 2,343 ms |
コンパイル使用メモリ | 216,164 KB |
実行使用メモリ | 29,992 KB |
最終ジャッジ日時 | 2024-09-25 13:37:53 |
合計ジャッジ時間 | 6,520 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 127 ms
17,740 KB |
testcase_14 | AC | 87 ms
17,760 KB |
testcase_15 | AC | 314 ms
29,992 KB |
testcase_16 | AC | 305 ms
29,864 KB |
testcase_17 | AC | 228 ms
24,956 KB |
testcase_18 | AC | 207 ms
24,252 KB |
testcase_19 | AC | 186 ms
24,012 KB |
testcase_20 | AC | 181 ms
24,188 KB |
testcase_21 | AC | 270 ms
28,820 KB |
testcase_22 | AC | 25 ms
7,072 KB |
testcase_23 | AC | 214 ms
24,020 KB |
testcase_24 | AC | 72 ms
13,404 KB |
testcase_25 | AC | 22 ms
6,940 KB |
testcase_26 | AC | 252 ms
26,528 KB |
testcase_27 | AC | 24 ms
6,944 KB |
testcase_28 | AC | 26 ms
8,180 KB |
testcase_29 | AC | 72 ms
13,316 KB |
testcase_30 | AC | 34 ms
8,668 KB |
testcase_31 | AC | 226 ms
24,144 KB |
ソースコード
#include<bits/stdc++.h> #define PPque priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<tuple<ll, ll, ll>>> #define Pque priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> #define pque priority_queue<ll, vector<ll>, greater<ll>> #define umap unordered_map #define uset unordered_set #define rep(i, s, f) for(ll i = s; i <= f; i++) #define per(i, s, f) for(ll i = s; i >= f; i--) #define all0(x) (x).begin() ,(x).end() #define all(x) (x).begin() + 1, (x).end() #define vvvvl vector<vvvl> #define vvvi vector<vector<vector<int>>> #define vvvl vector<vector<vector<ll>>> #define vvvc vector<vector<vector<char>>> #define vvvd vector<vector<vector<double>>> #define vvvm vector<vector<vector<mint>>> #define vvi vector<vector<int>> #define vvl vector<vector<ll>> #define vvs vector<vector<string>> #define vvc vector<vector<char>> #define vvp vector<vector<pair<ll, ll>>> #define vvb vector<vector<bool>> #define vvd vector<vector<double>> #define vvm vector<vector<mint>> #define vp vector<pair<ll, ll>> #define vi vector<int> #define vl vector<ll> #define vs vector<string> #define vc vector<char> #define vb vector<bool> #define vd vector<double> #define vm vector<mint> #define P pair<ll, ll> #define TU tuple<ll, ll, ll> #define rrr(l, r) mt()%(r-l+1)+l #define ENDL '\n' #define ull unsigned long long typedef long long ll; using namespace std; //////////////////////////////////////////////////////////////////////////////////////////////////////////// //これが本当の組み込み関数ってね(笑) template <typename T> T or_less(vector<T> &A, T x) { //x以下で最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), upper_bound(A.begin(), A.end(), x)-1); } template <typename T> T under(vector<T> &A, T x) { //x未満の最大要素の添字 前提: sort済み 存在しない: -1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)-1); } template <typename T> T or_more(vector<T> &A, T x) { //x以上で最小要素の添字 前提: sort済み 存在しない: N . //distanceのA.beginは添字を出すために常にA.begin() NG: A.begin() + 1 return distance(A.begin(), lower_bound(A.begin(), A.end(), x)); } template <typename T> T over(vector<T> &A, T x) { //xより大きい最小要素の添字前提: sort済み 存在しない: N return distance(A.begin(), upper_bound(A.begin(), A.end(), x)); } template <typename T> vector<T> vec_shift_right(vector<T> A, ll step, ll dir = 1, ll indexed = 1) {//dir = 1 : 右シフト dir = -1 : 左シフト ll N = A.size() - indexed; vector<T> res(N+1); rep(i, indexed, N) { ll idx = i - step * dir; if(idx < indexed) idx += N; if(idx > N) idx -= N; res.at(i) = A.at(idx); } return res; } template <typename T> void UNIQUE(vector<T> &A) { sort(all0(A)); return A.erase(unique(A.begin(), A.end()), A.end()); } template <typename T> void rev90(vector<vector<T>> &A, int indexed = 1) { reverse(A.begin() + indexed, A.end()); int n = A.size(); rep(i, indexed, n-1) { rep(j, i+1, n-1) { swap(A.at(i).at(j), A.at(j).at(i)); } } } void chmin(ll &a, ll b) { a = min(a, b); } void chmax(ll &a, ll b) { a = max(a, b); } ////////////////////////////////////////////////////////////////////// //数学系 /////////////////////////////////////////////////////////////////////// ll round(ll x, ll i) {return ll(x + 5 * pow(10, i-1))/ll(pow(10, i)) * ll(pow(10, i));} vp insu_bunkai(ll N) { vp res; for (ll i = 2; i * i <= N; i++) { ll cnt = 0; while(N % i == 0) { cnt++; N /= i; } if(cnt != 0) res.push_back(P(i, cnt)); } if(N != 1) res.push_back(P(N, 1)); return res; } ll extgcd (ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1;y = 0;return a;} ll d = extgcd(b, a%b, y, x); y -= a/b * x; return d; } template <typename T> T ceil(T a, T b) { assert(b != 0); if(a % b == 0) return a / b; if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b + 1; else return a / b; } template <typename T> T floor(T a, T b) { assert(b != 0); if(a % b == 0) return a / b; if((a <= 0 && b < 0) || (a >= 0 && b > 0)) return a/b; else return a/b - 1; } ll modpow(ll x, ll y, ll mod) { if(x > mod) x %= mod; if(y == 0) return 1; ll res = modpow(x, y >> 1, mod); res = res * res % mod; if(y & 1) res *= x, res %= mod; return res; } ll sqrt_(ll a) { ll l = 0; ll r = 3000000000LL; while(l < r) { ll mid = (l + r + 1) / 2; if(mid * mid <= a) l = mid; else r = mid - 1; } return l; } ////////////////////////////////////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //グローバル変数を置くところ(情報工学意識高め) //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") const ll int_max = 1001001001; const ll ll_max = 1001001001001001001LL; const double pi = 3.141592653589793; vl dx{0, 1, 0, -1, 0, 1, 1, -1, -1}; // (番兵) → ↓ ← ↑ ※ 右から時計回り vl dy{0, 0, -1, 0, 1, 1, -1, -1, 1}; //const ll mod = 1000000007; //const ll mod = 998244353; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void solve() { ll N, M; cin >> N >> M; vl A(N+1); rep(i,1,N)cin >> A[i]; umap<ll, ll> cnt; rep(i,1,N)cnt[A[i]]++; if(M%2 == 1) { cout << 0 << endl; return ; } ll ans = 0; rep(i, 1, N) {//対角線の一端を全探索、最後に/2 ll oppo = (A[i] + M/2); if(oppo > M) oppo -= M; ans += cnt[oppo] * (N - cnt[oppo] - 1); } cout << ans/2 << endl; } //無断で0を平方数にカウントする人もいる //”部分文字列”と”連続部分文字列”は違うので確認すること //一般のグラフと、有向辺かつその貼り方に制約がある(多くの場合:番号がで解放に伸びる)はだいぶ違うので確認すること //座標を2で割った時の”切り捨て側(左側)”を求めるには 誤:(x / 2) マイナスの時!!! 正:floor<ll>(x, 2); //stringでの数字の下から1桁目は 正:S.at(N-1) 誤:S.at(0) //if(S.at(i) == 1) ← charなのに1...? // modは取りましたか...?(´・ω・`) //sortの比較関数は、 a == b ならば falseを返す必要がある(そうで無いとRE(発生しない場合もある)) int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); ll T = 1; //cin >> T; rep(i, 1, T) { solve(); } return 0; }