oj.uz

Submission #362148

# Submission time Handle Problem Language Result Execution time Memory
362148 2021-02-01T20:40:08 Z ogibogi2004 Permutation Recovery (info1cup17_permutation) C++14
100 / 100
 2483 ms 12400 KB 
#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

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++)
      |              ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 1016 ms 6920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 1016 ms 6920 KB Output is correct
6 Correct 2421 ms 11412 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 1016 ms 6920 KB Output is correct
6 Correct 2421 ms 11412 KB Output is correct
7 Correct 2406 ms 12288 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 1016 ms 6920 KB Output is correct
6 Correct 2421 ms 11412 KB Output is correct
7 Correct 2406 ms 12288 KB Output is correct
8 Correct 1134 ms 5996 KB Output is correct
9 Correct 2212 ms 11872 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 492 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 11 ms 492 KB Output is correct
5 Correct 1016 ms 6920 KB Output is correct
6 Correct 2421 ms 11412 KB Output is correct
7 Correct 2406 ms 12288 KB Output is correct
8 Correct 1134 ms 5996 KB Output is correct
9 Correct 2212 ms 11872 KB Output is correct
10 Correct 2483 ms 12400 KB Output is correct