Submission #738340

#TimeUsernameProblemLanguageResultExecution timeMemory
738340billyismeMatching (CEOI11_mat)C++11
0 / 100
271 ms65536 KiB
#define TASK "text" #define INPUT TASK".INP" #define OUTPUT TASK".OUT" #include<bits/stdc++.h> using namespace std; bool multitest = false; #define int long long #define ll long long #define db double #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vll vector<ll> #define ve vector #define str string #define pb push_back #define pk pop_back #define el '\n' #define mp make_pair #define fi first #define se second #define tct template<typename T> #define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++) #define FORD(i,a,b) for(int i=(int)(a);i>=(int)(b);i--) #define FORN(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define all(a) a.begin(),a.end() #define btpc(a) __builtin_popcount(a) ll lg(ll a){return __lg(a);} ll sq(ll a){return a*a;} ll gcd(ll a , ll b){return __gcd(a,b);} ll lcm(ll a, ll b){return a/gcd(a,b)*b;} tct bool mini(T& a,const T& b){return (a>b)?a=b,1:0;} tct bool maxi(T& a,const T& b){return (a<b)?a=b,1:0;} tct void prt(T a[] ,int n ){FOR(i,1,n)cout<<a[i]<<" ";cout<<el;} int xx[] = {0,0,-1,0,1}; int yy[] = {0,-1,0,1,0}; const int N = 1e6+5, oo = 2e9, LO = 17; const ll inf = 1e17, cs = 330, sm = 1e9+7; const db PI = acos(-1), EPS = 1e-9; int n , m ; pii b[N] ; pii a[N] ; ll Hash_of_b = 0 ; vi value ; unordered_map<int,int>pos ; vi res; ll mu[N] ; struct Node { ll hash ; int sl ; } ; Node st[4*N] ; ll sum = 0; bool cmp(pii A , pii B) { return A.se<B.se ; } Node merge(Node L , Node R) { ll hash = (L.hash*mu[R.sl]%sm+R.hash)%sm ; int sl = L.sl+R.sl ; return {hash,sl} ; } void update(int id, int l ,int r ,int pos,int val , int sl ) { if(l==r&&l==pos) { st[id] = {val,sl} ; return ; } if(r<pos||pos<l)return ; int mid=(l+r)/2; update(id*2,l,mid,pos,val,sl) ; update(id*2+1,mid+1,r,pos,val,sl) ; st[id] =merge(st[id*2],st[id*2+1]) ; } void doc() { cin>> m >> n ; FOR(i,1,m)cin>>b[i].fi,b[i].se=i; FOR(i,1,n)cin>>a[i].fi,a[i].se=i ; } void xuly() { mu[0] = 1; FOR(i,1,n)mu[i] = mu[i-1]*cs%sm ; sort(b+1,b+m+1) ; FOR(i,1,m)Hash_of_b=(Hash_of_b*cs+b[i].se)%sm,sum=(sum+mu[i-1])%sm; sort(a+1,a+n+1) ; FOR(i,1,n)pos[a[i].se]=i ; FOR(i,1,m)update(1,1,n,pos[i],i,1); FOR(i,m,n) { ll d = (st[1].hash-1LL*(i-m)*sum%sm+sm)%sm; if(d==Hash_of_b)res.pb(i-m+1) ; update(1,1,n,pos[i-m+1],0,0) ; update(1,1,n,pos[i+1],i+1,1) ; } cout<<res.size()<<el; for(auto x:res)cout<<x<<" "; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if(fopen(INPUT,"r")) { freopen(INPUT ,"r",stdin); freopen(OUTPUT,"w",stdout); } int test =1; if(multitest)cin>>test; FOR(i,1,test) { doc() ; xuly() ; } cerr<<el<<"Time: "<<clock()<<"ms"<<el; }

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(INPUT ,"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
mat.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(OUTPUT,"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...
#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...