oj.uz

답안 #78387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78387 2018-10-04T15:56:23 Z igzi Zalmoxis (BOI18_zalmoxis) C++17
0 / 100
 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){
                ~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 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