oj.uz

Submission #362133

# Submission time Handle Problem Language Result Execution time Memory
362133 2021-02-01T20:07:59 Z ogibogi2004 Permutation Recovery (info1cup17_permutation) C++14
10 / 100
 8 ms 364 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=70004;
const int sq=500;
const ll mod=1e9+7;
int d[MAXN];
int d1[MAXN];
ll t[MAXN],n;
ll add(ll a,ll b)
{
	return (a+b+2*mod)%mod;
}
struct block
{
	unordered_map<int,vector<int> >mp;
	ll added;
};
block b[sq];
int p[MAXN];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{    
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++)
		{
		 	t[i]=(t[i]*10+s[j]-'0')%mod;
		}
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=add(t[i],-t[i-1]);
		d1[i]=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i/sq].added=0;
		b[i/sq].mp[d[i]].push_back(i);
	}
	//for(int i=1;i<=n;i++)cout<<d1[i]<<" ";
	//cout<<endl;
	for(int j=1;j<=n;j++)
	{
		for(int l=n/sq;l>=0;l--)
		{
			if(b[l].mp.count(1+b[l].added)&&b[l].mp[1+b[l].added].size()>0)
			{
				int t=b[l].mp[1+b[l].added].back();
				for(int i=l+1;i<=n/sq;i++)
				{
					b[i].added=add(b[i].added,d[t]);
				}
				for(int i=t+1;i<=n&&i%sq!=0;i++)
				{
					d1[i]-=d[t];
				}
				b[l].mp.clear();
				p[t]=j;
				for(int i=max(1,l*sq);i<=n&&i/sq==l;i++)
				{
					if(p[i]==0)b[i/sq].mp[d1[i]].push_back(i);
				}
				break;
			}
		}
		//for(int i=1;i<=n;i++)cout<<d1[i]<<" ";
		//cout<<endl;
	}
	for(int i=1;i<=n;i++)
	{
		cout<<p[i]<<" ";
	}
	cout<<endl;
return 0;
}

Compilation message

permutation.cpp: In function 'int main()':
permutation.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 8 ms 364 KB Output isn't correct