제출 #688223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
688223		alexdd	Permutation Recovery (info1cup17_permutation)	C++17	25 / 100	1 ms	340 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int bucket_size;
int update_timer;
int n;
int q[70001];

struct bucket
{
    int sum;
    vector<int> v;
};
bucket gol;

vector<bucket> buckets;
void balance_buckets()///O(n)
{
    vector<int> ramas;
    for(int i=0;i<buckets.size();i++)
        for(int j=0;j<buckets[i].v.size();j++)
            ramas.push_back(buckets[i].v[j]);
    buckets.clear();
    for(int i=0;i<ramas.size();i+=bucket_size)
    {
        buckets.push_back(gol);
        int limit = ramas.size()-1;
        limit = min(limit, i+bucket_size-1);
        for(int j=i;j<=limit;j++)
        {
            buckets[buckets.size()-1].v.push_back(ramas[j]);
            buckets[buckets.size()-1].sum = buckets[buckets.size()-1].sum + q[ramas[j]];
        }
    }
}

void insereaza(int b, int poz, int ramas)///O(marimea bucketului in care inserez)
{
    buckets[b].sum = buckets[b].sum + q[poz];
    for(int i=0;i<buckets[b].v.size();i++)
    {
        if(ramas==0)
        {
            buckets[b].v.insert(buckets[b].v.begin()+i, poz);
            return;
        }
        ramas = ramas - q[buckets[b].v[i]];
    }
    buckets[b].v.insert(buckets[b].v.end(), poz);
}

int rez[70001];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    bucket_size = sqrt(n);
    update_timer = sqrt(n);
    buckets.push_back(gol);
    int prec=0,ceva;
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
        ceva = q[i];
        q[i] = q[i] - prec;
        prec = ceva;

        int aux = q[i] - 1;
        int unde = 0;
        bool bl=0;
        for(int j=0;j<buckets.size();j++)
        {
            unde = j;
            if(aux - buckets[j].sum<=0)
            {
                bl=1;
                break;
            }
            aux = aux - buckets[j].sum;
        }
        insereaza(unde, i, aux);

        if(i<n && i%update_timer==0)
        {
            balance_buckets();
        }
    }

    int cate=0;
    for(int i=0;i<buckets.size();i++)
    {
        for(int j=0;j<buckets[i].v.size();j++)
        {
            cate++;
            rez[buckets[i].v[j]]=cate;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<rez[i]<<" ";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

permutation.cpp: In function 'void balance_buckets()':
permutation.cpp:21:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:22:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp:25:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<ramas.size();i+=bucket_size)
      |                 ~^~~~~~~~~~~~~
permutation.cpp: In function 'void insereaza(long long int, long long int, long long int)':
permutation.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<buckets[b].v.size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int j=0;j<buckets.size();j++)
      |                     ~^~~~~~~~~~~~~~~
permutation.cpp:71:14: warning: variable 'bl' set but not used [-Wunused-but-set-variable]
   71 |         bool bl=0;
      |              ^~
permutation.cpp:91:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<bucket>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<buckets.size();i++)
      |                 ~^~~~~~~~~~~~~~~
permutation.cpp:93:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j=0;j<buckets[i].v.size();j++)
      |                     ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6