제출 #132688

#제출 시각아이디문제언어결과실행 시간메모리
132688keko37Matching (CEOI11_mat)C++14
92 / 100
2011 ms54748 KiB
#include <bits/stdc++.h> using namespace std; typedef long long llint; const int MAXN = 1050005; const int MOD = 1000000007; const int B = 31337; int n, m, ofs; int p[MAXN], h[MAXN]; vector <int> saz, sol; llint val[MAXN * 2], pot[MAXN], sum[MAXN], roll; int br[MAXN * 2], prop[MAXN * 2]; inline llint mul (llint x, llint y) { return x * y % MOD; } inline llint add (llint x, llint y) { x += y; if (x >= MOD) return x - MOD; return x; } inline llint sub (llint x, llint y) { x -= y; if (x < 0) return x + MOD; return x; } void sazimanje () { for (int i=0; i<m; i++) { saz.push_back(h[i]); } sort(saz.begin(), saz.end()); for (int i=0; i<m; i++) { h[i] = lower_bound(saz.begin(), saz.end(), h[i]) - saz.begin(); } } void propagate (int x) { if (prop[x] == 0) return; if (x < ofs) { prop[2*x] += prop[x]; prop[2*x+1] += prop[x]; } val[x] = sub(val[x], mul(sum[br[x]], prop[x])); prop[x] = 0; } void update (int x, int pos, int low, int high, int k) { propagate(x); if (pos < low || high < pos) return; if (low == high) { val[x] = k; br[x] = (k > 0); return; } update(2*x, pos, low, (low + high)/2, k); update(2*x+1, pos, (low + high)/2+1, high, k); val[x] = add(mul(pot[br[2*x+1]], val[2*x]), val[2*x+1]); br[x] = br[2*x] + br[2*x+1]; } void smanji () { prop[1]++; } void build () { ofs = 1; while (ofs < m) ofs *= 2; for (int i=0; i<n; i++) { val[h[i] + ofs] = i+1; br[h[i] + ofs] = 1; } for (int i = ofs-1; i > 0; i--) { val[i] = add(mul(pot[br[2*i+1]], val[2*i]), val[2*i+1]); br[i] = br[2*i] + br[2*i+1]; } } void precompute () { roll = p[0]; pot[0] = 1; for (int i=1; i<n; i++) { pot[i] = mul(pot[i-1], B); sum[i] = add(sum[i-1], pot[i-1]); roll = add(mul(roll, B), p[i]); } } void ispis () { for (int i=1; i<2*ofs; i++) { cout << "t " << i << " " << val[i] << " " << br[i] << " " << prop[i] << endl; } } void rjesi () { if (val[1] == roll) sol.push_back(1); for (int i=1; i+n-1 < m; i++) { update(1, h[i-1], 0, ofs-1, 0); smanji(); update(1, h[i+n-1], 0, ofs-1, n); if (val[1] == roll) sol.push_back(i+1); } } inline bool is( char c ) { return c >= '0' && c <= '9'; } inline int read_int( ) { int num; char c; while( !is( c = getchar_unlocked( ) ) ); num = c - '0'; while( is( c = getchar_unlocked( ) ) ) num = num * 10 + c - '0'; return num; } #define pc(x) putchar_unlocked(x); inline void writeInt (int n) { int N = n, rev, count = 0; rev = N; if (N == 0) { pc('0'); pc('\n'); return ;} while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s rev = 0; while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;} //store reverse of N in rev while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;} while (count--) pc('0'); } int main () { n = read_int(); m = read_int(); for (int i=0; i<n; i++) { p[i] = read_int(); } for (int i=0; i<m; i++) { h[i] = read_int(); } sazimanje(); precompute(); build(); rjesi(); writeInt(sol.size()); putchar('\n'); for (int i=0; i<sol.size(); i++) { writeInt(sol[i]); putchar(' '); } return 0; }

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

mat.cpp: In function 'llint add(llint, llint)':
mat.cpp:23:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x >= MOD) return x - MOD; return x;
  ^~
mat.cpp:23:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x >= MOD) return x - MOD; return x;
                                ^~~~~~
mat.cpp: In function 'llint sub(llint, llint)':
mat.cpp:28:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (x < 0) return x + MOD; return x;
  ^~
mat.cpp:28:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (x < 0) return x + MOD; return x;
                             ^~~~~~
mat.cpp: In function 'int main()':
mat.cpp:144:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<sol.size(); i++) {
                ~^~~~~~~~~~~
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...