제출 #722700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722700		groshi	Restore Array (RMI19_restore)	C++17	100 / 100	13 ms	1312 KiB

restore

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int s[6000];
int sumy[6000];
int t[11000][5];
bool ustawione[6000];
struct wi{
    vector<int> Q;
    int odl=1e9;
    bool odw=0;
}*w;
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    int maxx=0;
    for(int i=1;i<=m;i++)
    cin>>t[i][0]>>t[i][1]>>t[i][2]>>t[i][3];
    for(int i=1;i<=m;i++)
    maxx=max(maxx,t[i][2]);
    bool brak=1;
    for(int i=1;i<=m;i++)
        if(t[i][2]!=1 && t[i][2]!=t[i][1]-t[i][0]+1)
            brak=0;
    if(n<=18 && m<=200)
    {
        for(int i=0;i<(1<<n);i++)
        {
            for(int j=0;j<n;j++)
            {
                int pom=i&(1<<j);
                if(pom>0)
                s[j]=1;
                else s[j]=0;
            }
            sumy[0]=s[0];
            for(int j=1;j<n;j++)
                sumy[j]=sumy[j-1]+s[j];
            bool git=0;
            for(int j=1;j<=m;j++)
            {
                int x=t[j][0];
                int y=t[j][1];
                int mam=sumy[y];
                if(x>0)
                    mam-=sumy[x-1];
                if(t[j][3]==0)
                {
                    if(mam<t[j][2])
                    {
                        git=1;
                        break;
                    }
                }
                else{
                    if(mam>t[j][2]-1)
                    {
                        git=1;
                        break;
                    }
                }
            }
            if(git==0)
            {
            for(int j=0;j<n;j++)
            cout<<!s[j]<<" ";
            cout<<"\n";
            return 0;
            }

        }
        cout<<"-1";
        return 0;
    }
    else if(maxx==1){
        for(int i=1;i<=m;i++)
            if(t[i][3]==1)
                for(int a=t[i][0];a<=t[i][1];a++)
                    s[a]=1;
        for(int i=1;i<=m;i++)
        {
            if(t[i][3]==0)
            {
                int suma=0;
                for(int a=t[i][0];a<=t[i][1];a++)
                    suma+=s[a];
                if(suma==t[i][1]-t[i][0]+1)
                {
                    cout<<"-1";
                    return 0;
                }
            }
        }
        for(int i=0;i<n;i++)
        cout<<s[i]<<" ";
    }
    else if(brak){
        bool git=0;
        for(int i=1;i<=m;i++)
        {
            if(t[i][3]==1 && t[i][2]==1)
                for(int a=t[i][0];a<=t[i][1];a++)
                {
                    if(ustawione[a]==1 && s[a]==0)
                    {
                        git=1;
                        break;
                    }
                    s[a]=1,ustawione[a]=1;
                }
            if(t[i][3]==0 && t[i][2]!=1)
                for(int a=t[i][0];a<=t[i][1];a++)
                {
                    if(s[a]==1)
                    {
                        git=1;
                        break;
                    }
                    ustawione[a]=1;
                }
            if(git)
            {
                cout<<"-1";
                return 0;
            }
        }
        for(int i=1;i<=m;i++)
        {
            bool git=0;
            if(t[i][3]==1 && t[i][2]==1)
                continue;
            if(t[i][3]==0 && t[i][2]!=1)
                continue;
            int chce=t[i][3];
            int puste=0;
            int gdzie=0;
            for(int a=t[i][0];a<=t[i][1];a++)
            {
                if(ustawione[a]==1 && s[a]==chce)
                {
                    git=1;
                    break;
                }
                if(ustawione[a]==0)
                {
                    puste++;
                    gdzie=a;
                }
            }
            if(git)
                continue;
            if(puste==0)
            {
                cout<<"-1";
                return 0;
            }
            if(puste==1)
            {
                ustawione[gdzie]=1;
                s[gdzie]=chce;
            }
        }
        int pop=0;
        for(int i=0;i<n;i++)
        {
            if(ustawione[i])
            continue;
            s[i]=pop;
            pop++;
            pop%=2;
        }
        for(int i=0;i<n;i++)
            cout<<s[i]<<" ";
        return 0;
    }
    else{
            int a,b,c,d;
        w=new wi[n+3];
    w[0].Q.push_back(1);
    w[0].Q.push_back(0);
    for(int i=1;i<n;i++)
    {
        w[i].Q.push_back(i+1);
        w[i].Q.push_back(1);
    }
    for(int i=n;i>=1;i--)
    {
        w[i].Q.push_back(i-1);
        w[i].Q.push_back(0);
    }
    for(int i=1;i<=m;i++)
    {
        a=t[i][0];
        b=t[i][1];
        c=t[i][2];
        d=t[i][3];
        a++;
        b++;
        if(d==1)
        {
            w[b].Q.push_back(a-1);
            w[b].Q.push_back(-(b-a+1)+c-1);
        }
        else{
            w[a-1].Q.push_back(b);
            w[a-1].Q.push_back(b-a+1-c);
        }
    }
    priority_queue<pair<int,int> > kolejka;
    kolejka.push({0,0});
    w[0].odl=0;
    bool k=0;
    while(!kolejka.empty())
    {
        auto para=kolejka.top();
        kolejka.pop();
        w[para.second].odw=1;
        for(int i=0;i<w[para.second].Q.size();i+=2)
        {
            if(w[para.second].odl+w[para.second].Q[i+1]<w[w[para.second].Q[i]].odl)
            {
                w[w[para.second].Q[i]].odl=w[para.second].odl+w[para.second].Q[i+1];
                auto parap=make_pair(w[w[para.second].Q[i]].odl*(-1),w[para.second].Q[i]);
                kolejka.push(parap);
            }
            if(w[w[para.second].Q[i]].odw && w[w[para.second].Q[i]].odl<0)
            {
                k=1;
                break;
            }
        }
        if(k==1)
            break;
    }
    if(k==1)
        cout<<"-1";
    else{
        for(int i=1;i<=n;i++)
        {
            cout<<w[i].odl-w[i-1].odl<<" ";
        }
    }
    return 0;
    }
    return 0;
}

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

restore.cpp: In function 'int32_t main()':
restore.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         for(int i=0;i<w[para.second].Q.size();i+=2)
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55