Submission #711340
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < n; i++) #define all(x) x.begin(), x.end() #define Min(x) *min_element(all(x)) #define Max(x) *max_element(all(x)) template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) { o << "(" << v.first << ", " << v.second << ")"; return o; } template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { if (!v.empty()) { o << '['; copy(v.begin(), v.end(), ostream_iterator<T>(o, ", ")); o << "\b\b]"; } return o; } using ll = long long; using ld = long double; using vll = vector<ll>; using vi = vector<int>; typedef pair<int, int> P; static const double EPS = 1e-14; static const long long INF = 1e18; #define MAX_N 100005 ll n; vll a; bool check(ll l) // l個切り出せるなら1 { if (l > n) return false; unordered_map<ll, int> s; rep(i, l) s[a[i]]++; if (s.size() == l) return true; rep(i, n-l) { s[a[i]]--; if (!s[a[i]]) s.erase(a[i]); s[a[i+l]]++; if (s.size() == l) return true; } return false; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); n; cin >> n; a = vll(n); rep(i, n) cin >> a[i]; // デバッグはここでチェック関数を確認するといい /* while (1) { ll t; cin >> t; cout << check(t) << endl; } */ // 構造は11111000000なら、!check(mid) // lは最大の満たさない場所、rは最小の満たす場所。 ll lo = 1, ro = n+1; // lが満たさないことを確認! while (ro - lo != 1) { ll mid = (lo + ro) / 2; // check関数が単純ならここに書いてもいいが、デバッグしにくくなるので関数は分けるべき !check(mid)?ro=mid:lo=mid; } cout << lo << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 細長いお菓子 |
User | hamko |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1917 Byte |
Status | AC |
Exec Time | 426 ms |
Memory | 5784 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 49 / 49 | 1 / 1 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt |
Subtask3 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 27 ms | 876 KB |
sample_02.txt | AC | 23 ms | 924 KB |
subtask1_01.txt | AC | 23 ms | 920 KB |
subtask1_02.txt | AC | 25 ms | 920 KB |
subtask1_03.txt | AC | 34 ms | 908 KB |
subtask1_04.txt | AC | 27 ms | 820 KB |
subtask1_05.txt | AC | 27 ms | 920 KB |
subtask1_06.txt | AC | 24 ms | 872 KB |
subtask1_07.txt | AC | 27 ms | 816 KB |
subtask1_08.txt | AC | 27 ms | 876 KB |
subtask1_09.txt | AC | 28 ms | 924 KB |
subtask1_10.txt | AC | 26 ms | 920 KB |
subtask1_11.txt | AC | 28 ms | 924 KB |
subtask1_12.txt | AC | 28 ms | 920 KB |
subtask2_01.txt | AC | 28 ms | 864 KB |
subtask2_02.txt | AC | 29 ms | 876 KB |
subtask2_03.txt | AC | 28 ms | 872 KB |
subtask2_04.txt | AC | 26 ms | 880 KB |
subtask2_05.txt | AC | 26 ms | 924 KB |
subtask2_06.txt | AC | 26 ms | 876 KB |
subtask2_07.txt | AC | 29 ms | 872 KB |
subtask2_08.txt | AC | 29 ms | 876 KB |
subtask2_09.txt | AC | 29 ms | 924 KB |
subtask2_10.txt | AC | 29 ms | 880 KB |
subtask3_01.txt | AC | 89 ms | 1128 KB |
subtask3_02.txt | AC | 161 ms | 2156 KB |
subtask3_03.txt | AC | 176 ms | 2168 KB |
subtask3_04.txt | AC | 393 ms | 3320 KB |
subtask3_05.txt | AC | 426 ms | 3324 KB |
subtask3_06.txt | AC | 352 ms | 3324 KB |
subtask3_07.txt | AC | 389 ms | 5784 KB |