Submission #362148

#TimeUsernameProblemLanguageResultExecution timeMemory
362148ogibogi2004Permutation Recovery (info1cup17_permutation)C++14
100 / 100
2483 ms12400 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=70004; const ll mod1=1e9+9; const ll mod2=1e9+7; const ll sq=300; ll d1[MAXN]; ll d2[MAXN]; ll dd1[MAXN],e; ll dd2[MAXN]; ll t1[MAXN],n; ll t2[MAXN]; ll add1(ll a,ll b) { return (a+b+2*mod1)%mod1; } ll add2(ll a,ll b) { return (a+b+2*mod2)%mod2; } ll tr(pair<ll,ll> p) { return p.first*(mod1+1)+p.second; } struct block { unordered_map<ll,vector<ll> >mp; ll added1; ll added2; }; block b[sq]; ll p[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); srand(3432);e=rand(); ll ee=rand(); cin>>n; for(ll i=1;i<=n;i++) { string s; cin>>s; for(ll j=0;j<s.size();j++) { t1[i]=add1(t1[i]*10,s[j]-'0'); t2[i]=add2(t2[i]*10,s[j]-'0'); } } for(ll i=1;i<=n;i++) { d1[i]=add1(t1[i],-t1[i-1]); d2[i]=add2(t2[i],-t2[i-1]); dd1[i]=d1[i]; dd2[i]=d2[i]; } for(ll i=1;i<=n;i++) { b[i/sq].added1=0; b[i/sq].added2=0; b[i/sq].mp[tr({d1[i]^e,d2[i]^ee})].push_back(i); } //for(ll i=1;i<=n;i++)cout<<dd1[i]<<" "; //cout<<endl; for(ll j=1;j<=n;j++) { for(ll l=n/sq;l>=0;l--) { if(b[l].mp.count(tr({add1(1,b[l].added1)^e,add2(1,b[l].added2)^ee}))&&b[l].mp[tr({add1(1,b[l].added1)^e,add2(1,b[l].added2)^ee})].size()>0) { ll t=b[l].mp[tr({add1(1,b[l].added1)^e,add2(1,b[l].added2)^ee})].back(); for(ll i=l+1;i<=n/sq;i++) { b[i].added1=add1(b[i].added1,d1[t]); b[i].added2=add2(b[i].added2,d2[t]); } for(ll i=t+1;i<=n&&i%sq!=0;i++) { dd1[i]=add1(dd1[i],-d1[t]); dd2[i]=add2(dd2[i],-d2[t]); } b[l].mp.clear(); p[t]=j; for(ll i=max(1ll,l*sq);i<=n&&i/sq==l;i++) { if(p[i]==0)b[i/sq].mp[tr({dd1[i]^e,dd2[i]^ee})].push_back(i); } break; } } //for(ll i=1;i<=n;i++)cout<<dd1[i]<<" "; //cout<<endl; } for(ll i=1;i<=n;i++) { cout<<p[i]<<" "; } cout<<endl; return 0; }

Compilation message (stderr)

permutation.cpp: In function 'int main()':
permutation.cpp:46:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(ll j=0;j<s.size();j++)
      |              ~^~~~~~~~~
#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...