Submission #1060095

#TimeUsernameProblemLanguageResultExecution timeMemory
1060095Zbyszek99Lottery (CEOI18_lot)C++17
20 / 100
3056 ms7652 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define size(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace std; //mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll rand(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; ll pot[100000]; int ans[2000][2000]; void solve() { int n,l; cin >> n >> l; int max_s = n-l+1; vector<ll> v(n); rep(i,n) cin >> v[i]; int q; cin >> q; int z; if(q == 1) { cin >> z; if(z == 0) { map<ll,int> counter; map<int,ll> h; rep(i,max_s) { ll hash = 0; rep(k,l) { hash += v[i+k] * pot[k]; hash %= MOD; } counter[hash]++; h[i] = hash; } rep(i,max_s) { cout << counter[h[i]]-1 << " "; } return; } } rep(i,max_s) { rep(j,max_s) { if(i == j) continue; int dist = 0; rep(k,l) { if(v[i+k] != v[j+k]) dist++; } ans[i][j] = dist; } } rep(qq,q) { int k; if(qq == 0) k = z; else cin >> k; rep(i,max_s) { int a = 0; rep(j,max_s) { if(i == j) continue; if(ans[i][j] <= k) a++; } cout << a << " "; } cout << "\n"; } } int main() { pot[0] = 1; rep2(i,1,100000) { pot[i] = pot[i-1] * 2137; pot[i] %= MOD; } ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random(); int t = 1; //cin >> t; while(t--) solve(); }

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:98:16: warning: iteration 99999 invokes undefined behavior [-Waggressive-loop-optimizations]
   98 |         pot[i] = pot[i-1] * 2137;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:10:38: note: within this loop
   10 | #define rep2(i,a,b) for(int i = a; i <= (b); ++i)
      |                                      ^
lot.cpp:96:5: note: in expansion of macro 'rep2'
   96 |     rep2(i,1,100000)
      |     ^~~~
#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...