제출 #788652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788652		mosiashvililuka	죄수들의 도전 (IOI22_prison)	C++17	90 / 100	144 ms	1932 KiB

prison

#include<bits/stdc++.h>
#include "prison.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,s[5009][5009],mid,l,r,MX;
vector <pair <int, int> > V[5009];
int fun(int q){
    if(q==0) return -1; else return -2;
}
std::vector<std::vector<int> > devise_strategy(int NN) {
    a=NN;
    //sawyisi 0
    s[0][0]=0;//A
    for(i=1; i<=a; i++){
        if(i==1){
            s[0][i]=-1;
            continue;
        }
        if(i==a){
            s[0][i]=-2;
            continue;
        }
        mid=(2+(a-1))/2;
        if(i<=mid){
            s[0][i]=1;MX=max(MX,1);
        }else{
            s[0][i]=2;MX=max(MX,2);
        }
    }
    V[1].push_back({2,a-1});   //1/2+1%2 da 2/2+2%2

    //MX=2;
    for(ii=1; ii<=MX; ii++){
        c=ii/2+ii%2;
        if(c%2==0){
            s[ii][0]=0;
        }else{
            s[ii][0]=1;
        }

        for(i=1; i<=a; i++){
            e=0;
            for(j=0; j<V[c].size(); j++){
                l=V[c][j].first;r=V[c][j].second;
                if(l-1<=i&&i<=r+1){
                    e=1;break;
                }
            }
            if(e==0){
                s[ii][i]=0;continue;
            }
            //l r gaq
            mid=(l+r)/2;
            if(ii%2==1){
                r=mid;
            }else{
                l=mid+1;
            }

            if(i<=l){
                s[ii][i]=fun(s[ii][0]);
                continue;
            }
            if(i>=r){
                s[ii][i]=fun(1-s[ii][0]);
                continue;
            }
            l++;r--;
            //MX=max(MX,ii+2);
            mid=(l+r)/2;
            if(i<=mid){
                s[ii][i]=c*2+1;
                MX=max(MX,c*2+1);
            }else{
                s[ii][i]=c*2+2;
                MX=max(MX,c*2+2);
            }
            V[c+1].push_back({l,r});
        }
    }


    vector <vector <int> > ANSA;
    ANSA.resize(MX+1);
    for(i=0; i<ANSA.size(); i++){
        ANSA[i].resize(a+1);
    }

    for(i=0; i<ANSA.size(); i++){
        for(j=0; j<=a; j++){
            ANSA[i][j]=s[i][j];
        }
    }


    /*cout<<ANSA.size()<<"\n";
    for(i=0; i<ANSA.size(); i++){
        for(j=0; j<=a; j++){
            cout<<ANSA[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    return ANSA;
}

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

prison.cpp: In function 'std::vector<std::vector<int> > devise_strategy(int)':
prison.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for(j=0; j<V[c].size(); j++){
      |                      ~^~~~~~~~~~~~
prison.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(i=0; i<ANSA.size(); i++){
      |              ~^~~~~~~~~~~~
prison.cpp:88:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(i=0; i<ANSA.size(); i++){
      |              ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 80 / 90