- /**
- * CTU Open 2017
- * Problem Solution: Ice cream samples
- * Idea: Use two pointers to consecutively enlarge/shorten result interval - linear time solution
- * @author Josef Malik
- */
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <sstream>
- #include <map>
- #include <set>
- #include <queue>
- #include <vector>
- using namespace std;
- typedef long long int ll;
- typedef pair<int, int> pii;
- #define PB push_back
- #define MP make_pair
- #define FOR(prom, a, b) for(int prom = (a); prom < ((int)(b)); prom++)
- #define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
- #define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
- #define R1(a) do{scanf("%d", &(a));}while(0)
- #define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0)
- #define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0)
- #define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0)
- #define MM(co, cim) memset((co), (cim), sizeof((co)))
- #define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
- #define INF 1000000007
- int n, k, li, p1, p2, ct[1000014], ctu, ctc, res;
- vector<int> st[1000014];
- int main ()
- {
- while (scanf("%d%d", &n, &k) != -1)
- {
- FOR(i, 0, n) st[i].clear();
- FOR(i, 0, n)
- {
- R1(li);
- FOR(j, 0, li) SV(st[i]);
- }
- res = INF;
- MM(ct, 0);
- p1 = ctc = ctu = 0;
- p2 = -1;
- while (p1 < 2 * n)
- {
- if (p2 == 2 * n - 1 || p2 - p1 + 1 >= n || ctu == k)
- {
- if (ctu == k) res = min(res, ctc);
- FOR(i, 0, st[p1 % n].size())
- {
- if (--ct[st[p1 % n][i]]);else --ctu;
- --ctc;
- }
- ++p1;
- }
- else
- {
- ++p2;
- FOR(i, 0, st[p2 % n].size())
- {
- if (++ct[st[p2 % n][i]] == 1) ++ctu;
- ++ctc;
- }
- }
- }
- printf("%d\n", res == INF ? -1 : res);
- }
- return 0;
- }
双指针
From Bistre Pheasant, 3 Years ago, written in Plain Text, viewed 303 times.
URL http://axuhongbo.top/paste/view/7044a4f6
Embed
Download Paste or View Raw
— Expand Paste to full width of browser