제출 #71047

#제출 시각아이디문제언어결과실행 시간메모리
71047qkxwsmLottery (CEOI18_lot)C++17
100 / 100
1512 ms9148 KiB
/* PROG: source LANG: C++11 _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } int operator()(long long x) const { return x ^ (x >> 32); } }; template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>; template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T, class U> T normalize(T x, U mod = 1000000007) { return (((x % mod) + mod) % mod); } long long randomizell(long long mod) { return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod; } int randomize(int mod) { return ((1ll << 15) * rand() + rand()) % mod; } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll #define MAXN 10013 #define MAXQ 113 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; int N, L, Q; int arr[MAXN]; vector<int> compress; int quer[MAXN]; int di[MAXN]; vector<pii> queries; int sup[MAXN]; int pos[MAXN]; int pre[MAXN][MAXQ]; int32_t main() { ios_base::sync_with_stdio(0); srand(time(0)); // cout << fixed << setprecision(10); // cerr << fixed << setprecision(10); if (fopen("input.in", "r")) { freopen ("input.in", "r", stdin); freopen ("output.out", "w", stdout); } cin >> N >> L; compress.reserve(N); for (int i = 0; i < N; i++) { cin >> arr[i]; compress.PB(arr[i]); } sort(compress.begin(), compress.end()); compress.erase(unique(compress.begin(), compress.end()), compress.end()); for (int i = 0; i < N; i++) { arr[i] = LB(compress.begin(), compress.end(), arr[i]) - compress.begin(); } cin >> Q; for (int i = 0; i < Q; i++) { cin >> quer[i]; queries.PB({quer[i], i}); } sort(queries.begin(), queries.end()); for (int i = 0; i < Q; i++) { pos[queries[i].se] = i; } for (int i = 0; i <= L; i++) { sup[i] = queries.size(); } for (int i = 0; i < queries.size(); i++) { int lo = ((i == 0) ? 0 : (queries[i - 1].fi + 1)); for (int j = lo; j <= queries[i].fi; j++) { sup[j] = i; } } // for (int i = 0; i <= N - L; i++) // { // for (int j = 0; j <= N - L; j++) // { // if (i == 0) // { // // for (int k = 0; k < L; k++) // { // if (arr[i + k] != arr[j + k]) // { // dist[i][j]++; // } // } // } // else if (j == 0) // { // dist[i][j] = dist[j][i]; // } // else // { // dist[i][j] = dist[i - 1][j - 1] + (bool) (arr[i + L - 1] != arr[j + L - 1]) - (bool) (arr[i - 1] != arr[j - 1]); // } // // cerr << dist[i][j] << ' '; // pre[i][sup[dist[i][j]] + 1]++; // } // // cerr << endl; // } for (int i = -(N - L); i <= (N - L); i++) { for (int j = 0; j <= N - L; j++) { di[j] = -1; } for (int j = 0; j <= N - L; j++) { if (j + i < 0 || j + i > N - L) { continue; } di[j] = 0; int x = j + i; if (j == 0 || di[j - 1] == -1) { for (int k = 0; k < L; k++) { if (arr[j + k] != arr[x + k]) { di[j]++; } } } else { di[j] = di[j - 1] + (bool) (arr[j + L - 1] != arr[x + L - 1]) - (bool) (arr[j - 1] != arr[x - 1]); } pre[j][sup[di[j]] + 1]++; } //lo...lo + i } for (int i = 0; i <= N - L; i++) { for (int j = 1; j <= Q + 1; j++) { pre[i][j] += pre[i][j - 1]; } } for (int i = 0; i < Q; i++) { for (int j = 0; j <= N - L; j++) { if (j) cout << ' '; cout << pre[j][pos[i] + 1] - 1; } cout << '\n'; } //they differ in less than x positions //pos i, diff j // cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

lot.cpp: In function 'int32_t main()':
lot.cpp:193:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < queries.size(); i++)
                         ~~^~~~~~~~~~~~~~~~
lot.cpp:162:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
                 freopen ("input.in", "r", stdin);
                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lot.cpp:163:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
                 freopen ("output.out", "w", stdout);
                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...