Submission #144156

#TimeUsernameProblemLanguageResultExecution timeMemory
144156SwanLottery (CEOI18_lot)C++14
25 / 100
75 ms636 KiB
#include <bits/stdc++.h> #define stop system("pause") #define INP freopen("input.txt","r",stdin) #define OUTP freopen("solve1.txt","w",stdout) using namespace std; typedef long long ll; vector<int> seq[400]; vector<int> v; int n,l; ll mod = 1e9+7; ll pwr = 51; ll pw[20000]; ll get_val[20000]; unordered_map<ll,int> cnt; ll mul(ll a,ll b){ a%=mod; b%=mod; return (a*b)%mod; } ll pl(ll a,ll b){ return (a+b)%mod; } int val(vector<int>& a,vector<int>& b,int k){ int res = 0; for(int i(0); i < a.size();i++){ if(a[i]!=b[i])res++; } return res<=k; } void get_hash(vector<int>& v,int id){ ll hs = 0; for(int i(0); i < v.size();i++){ hs = pl(hs,mul(v[i],pw[i])); } get_val[id] = hs; cnt[hs]++; } void brute(){ pw[0] = 1; for(int i(1); i < 20000;i++){ pw[i] = mul(pw[i-1],pwr); } for(int i(0); i < n;i++){ int r = i+l-1; if(r >= n)break; for(int j(i);j<=r;j++){ seq[i].push_back(v[j]); } get_hash(seq[i],i); } int q; cin >> q; if(q == 1){ int k; cin >> k; if(k == 0){ for(int i(0); i < n-l+1;i++)cout << cnt[get_val[i]]-1 << ' '; exit(0); } } for(int i(0); i < q;i++){ int k; cin >> k; for(int j(0); j < n-l+1;j++){ int ans = 0; for(int z(0); z < n-l+1;z++){ if(j == z)continue; ans+=val(seq[j],seq[z],k); } cout << ans << ' '; } cout << '\n'; } } main() { ios_base::sync_with_stdio(0); cin >> n >> l; for(int i(0); i < n;i++){ int x; cin >> x; v.push_back(x); } if(n<=300)brute(); return 0; } /* 8 2 1 2 3 1 3 1 2 3 1 0 */

Compilation message (stderr)

lot.cpp: In function 'int val(std::vector<int>&, std::vector<int>&, int)':
lot.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < a.size();i++){
                   ~~^~~~~~~~~~
lot.cpp: In function 'void get_hash(std::vector<int>&, int)':
lot.cpp:38:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v.size();i++){
                   ~~^~~~~~~~~~
lot.cpp: At global scope:
lot.cpp:80:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
#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...