| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 78387 |
2018-10-04T15:56:23 Z |
igzi |
Zalmoxis (BOI18_zalmoxis) |
C++17 |
|
1000 ms |
70200 KB |
#include <bits/stdc++.h>
#include <ext/rope>
#define maxN 1000005
#define s 4294967296
using namespace std;
using namespace __gnu_cxx;
int n,k,i,x,p;
priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int f[maxN];
void update(int p){
while(p<=n){
f[p]++;
p+=p & (-p);
}
}
int query(int p){
int ans=0;
while(p>0){
ans+=f[p];
p-=p &(-p);
}
return ans;
}
struct broj{
int b;
int sl;
};
broj v[maxN];
rope <long long> r;
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>k;
cin>>x;
pq.push({x,i});
p=0;
r.insert(r.mutable_end(),s*x+p);
v[0].b=x;
v[0].sl=-1;
p=1;
for(i=1;i<n;i++){
cin>>x;
pq.push({x,i});
v[p].b=x;
v[p-1].sl=p;
r.insert(r.mutable_end(),s*x+p);
p++;
}
v[p-1].sl=-1;
//for(i=0;i<n;i++) cout<<r[i]/s<<" ";
while(k>0){
long long tmp=pq.top().second;
pq.pop();
x=tmp-query(tmp);
if((x==r.size()-1 || r[x+1]/s!=r[x]/s) && (x==0 || r[x-1]/s!=r[x]/s)){
broj c;
c.sl=v[r[x]%s].sl;
c.b=r[x]/s;
pq.push({c.b,tmp});
v[p]=c;
v[r[x]%s].sl=p;
tmp=(r[x]/s+1)*s+p;
p++;
//cout<<r[x]/s<<" "<<tmp/s<<endl;
r.erase(x,1);
r.insert(r.mutable_begin()+x,tmp);
}
else{
if(x!=r.size()-1 && r[x+1]/s==r[x]/s){
update(r[x+1]%s);
broj c;
c.sl=v[r[x+1]%s].sl;
c.b=r[x+1]/s+1;
pq.push({c.b,tmp});
v[p]=c;
v[r[x+1]%s].sl=p;
tmp=(r[x]/s+1)*s+p;
p++;
r.erase(x,1);
r.insert(r.mutable_begin()+x,tmp);
r.erase(x+1,1);
}
else{
update(r[x-1]%s);
broj c;
c.sl=v[r[x-1]%s].sl;
c.b=r[x-1]/s+1;
pq.push({c.b,tmp});
v[p]=c;
v[r[x-1]%s].sl=p;
tmp=(r[x]/s+1)*s+p;
p++;
r.erase(x,1);
r.insert(r.mutable_begin()+x,tmp);
r.erase(x-1,1);
}
}
k--;
}
int x=0;
while(x!=-1){
cout<<v[x].b<<" ";
x=v[x].sl;
}
return 0;
}
Compilation message
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:58:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if((x==r.size()-1 || r[x+1]/s!=r[x]/s) && (x==0 || r[x-1]/s!=r[x]/s)){
~^~~~~~~~~~~~
zalmoxis.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x!=r.size()-1 && r[x+1]/s==r[x]/s){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
551 ms |
43020 KB |
not a zalsequence |
| 2 |
Incorrect |
556 ms |
45088 KB |
not a zalsequence |
| 3 |
Incorrect |
577 ms |
47428 KB |
not a zalsequence |
| 4 |
Incorrect |
550 ms |
49476 KB |
not a zalsequence |
| 5 |
Incorrect |
561 ms |
51508 KB |
not a zalsequence |
| 6 |
Incorrect |
538 ms |
53416 KB |
not a zalsequence |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
534 ms |
55524 KB |
not a zalsequence |
| 2 |
Incorrect |
552 ms |
57532 KB |
not a zalsequence |
| 3 |
Incorrect |
551 ms |
59828 KB |
not a zalsequence |
| 4 |
Incorrect |
541 ms |
61776 KB |
not a zalsequence |
| 5 |
Incorrect |
508 ms |
63764 KB |
not a zalsequence |
| 6 |
Incorrect |
544 ms |
65976 KB |
not a zalsequence |
| 7 |
Incorrect |
545 ms |
68092 KB |
not a zalsequence |
| 8 |
Incorrect |
557 ms |
70200 KB |
not a zalsequence |
| 9 |
Incorrect |
971 ms |
70200 KB |
not a zalsequence |
| 10 |
Execution timed out |
1080 ms |
70200 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1074 ms |
70200 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1077 ms |
70200 KB |
Time limit exceeded |
| 13 |
Incorrect |
597 ms |
70200 KB |
not a zalsequence |
| 14 |
Incorrect |
277 ms |
70200 KB |
not a zalsequence |
