結果
問題 | No.647 明太子 |
ユーザー | yocchi |
提出日時 | 2018-02-09 23:11:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,389 ms / 4,500 ms |
コード長 | 2,596 bytes |
コンパイル時間 | 1,165 ms |
コンパイル使用メモリ | 101,288 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-09 09:26:36 |
合計ジャッジ時間 | 6,652 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 14 ms
4,376 KB |
testcase_10 | AC | 33 ms
4,380 KB |
testcase_11 | AC | 8 ms
4,376 KB |
testcase_12 | AC | 24 ms
4,376 KB |
testcase_13 | AC | 58 ms
4,376 KB |
testcase_14 | AC | 683 ms
4,376 KB |
testcase_15 | AC | 89 ms
4,380 KB |
testcase_16 | AC | 23 ms
4,376 KB |
testcase_17 | AC | 857 ms
4,380 KB |
testcase_18 | AC | 944 ms
4,376 KB |
testcase_19 | AC | 212 ms
4,376 KB |
testcase_20 | AC | 276 ms
4,380 KB |
testcase_21 | AC | 88 ms
4,376 KB |
testcase_22 | AC | 1,389 ms
4,380 KB |
testcase_23 | AC | 3 ms
4,380 KB |
ソースコード
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <map> #include <vector> #include <deque> #include <list> #include <stack> #include <queue> #include <set> #include <algorithm> #include <iostream> #include <iterator> #include <memory> using namespace std; #if 1 #define PRINT(x) { cout << #x << ": " << (x) << endl; } #define PRINT_CONTAINER(x) { cout << #x << ": "; \ for (size_t ix = 0; ix < (x).size(); ++ix) cout << (x)[ix] << ", "; \ cout << endl; } #else #define PRINT(x) #define PRINT_CONTAINER(x) #endif typedef pair<int, int> p; int n, m; vector<p> member; vector<p> mentai_a; vector<p> mentai_b; vector<p> vote; int main(int argc, char *argv[]) { scanf("%d", &n); for (int i = 0; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); member.push_back(p(a, b)); } scanf("%d", &m); for (int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); mentai_a.push_back(p(a, i)); mentai_b.push_back(p(b, i)); vote.push_back(p(0, i)); } sort(mentai_a.begin(), mentai_a.end()); sort(mentai_b.begin(), mentai_b.end()); for (int i = 0; i < n; ++i) { auto it_a = upper_bound(mentai_a.begin(), mentai_a.end(), p(member[i].first+1, 0)); set<int> fav_a; for (auto it = mentai_a.begin(); it != it_a; ++it) { // cout << i << ",a " << it->second << it->first << endl; fav_a.insert(it->second); } auto it_b = lower_bound(mentai_b.begin(), mentai_b.end(), p(member[i].second, 0)); set<int> fav_b; for (auto it = it_b; it != mentai_b.end(); ++it) { // cout << i << ",b " << it->second << endl; fav_b.insert(it->second); } vector<int> fav; set_intersection(fav_a.begin(), fav_a.end(), fav_b.begin(), fav_b.end(), back_inserter(fav)); for (int v : fav) { ++vote[v].first; } } sort(vote.begin(), vote.end()); reverse(vote.begin(), vote.end()); // for (auto v : vote) // { // cout << v.first << ", " << v.second << endl; // } int vmax = vote[0].first; if (vmax == 0) { puts("0"); return 0; } vector<int> vv; for (int i = 0; i < m; ++i) { if (vote[i].first != vmax) break; vv.push_back(vote[i].second); } sort(vv.begin(), vv.end()); for (auto v : vv) { printf("%d\n", v + 1); } return 0; }