제출 #1191859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191859		Amr	죄수들의 도전 (IOI22_prison)	C++20	0 / 100	1094 ms	19012 KiB

prison

#include "prison.h"
#include <vector>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()

vector<vector<int > > ans;
ll go(ll x)
{
    if(x==0) return -1;
    if(x==1) return -2;
}
ll mx = 0;
void fun(ll x, vector<pair<ll,ll> > segs, ll bag , ll wh, ll num , ll lst)
{

    mx = max(mx,lst);
    if(num>0)
    {
        ans[x][0] = wh;

        ll L = segs[0].F, R = segs[0].S;
        ans[x][L] = go(wh);
        ans[x][R] = go(!wh);

        vector<pair<ll,ll> > newsegs;
        ll currbag;
        //if(x==1) cout << L << " " << R << endl;
        L++,R--;
        if(L==R)
        {
            newsegs.push_back({L,R});
        }
        else if(R-L==1)
        {
            newsegs.push_back({L,L});
            newsegs.push_back({R,R});
        }
        else if(R-L>=2)
        {
            ll mid1 = L+(R-L+1)/3-1;
            ll mid2 = mid1+(R-L+1)/3;
            newsegs.push_back({L,mid1});
            newsegs.push_back({mid1+1,mid2});
            newsegs.push_back({mid2+1,R});
        }
        else return;
        for(int i = 0; i < newsegs.sz; i++)
        {
            ll l = newsegs[i].F , r = newsegs[i].S;
            if(num>=l&&num<=r) currbag = i+1;
        }
        ans[x][num] = lst+currbag;
        fun(x, newsegs,currbag,!wh,0,lst+newsegs.sz);
    }
    else
    {
        //ans[x][0] = wh;
        ll L = segs[0].F , R =segs.back().S;
        ans[x+bag][L-1] = go(wh); if(x==1) cout  << L << " " << R << endl;
        ans[x+bag][R+1] = go(!wh);
        for(int j = L; j <= R; j++) {
            ll currbag; ll l2, r2;
        for(int i = 0; i < segs.sz; i++)
        {
            ll l = segs[i].F;
            ll r = segs[i].S;
            if(j>=l&&j<=r) currbag = i+1,l2 = l, r2= r;
        }
        if(currbag<bag) ans[x+bag][j] = go(wh);
        else if(currbag>bag) ans[x+bag][j] = go(!wh);
        else{
        //ans[x+bag][j] = x+currbag;
        fun(x+bag, vector<pair<ll,ll> > ({{l2,r2}}), -1, wh, j, lst);}
        }

    }
}
std::vector<std::vector<int>> devise_strategy(int N) {


    ans.resize(N+1,vector<int> (N+1,0));
    ans[0][1] = go(0);
    ans[0][N] = go(1);
    ans[0][0] = 0;
    for(int i = 2; i <= N-1; i++) fun(0,{{1,N}},-1,0,i,0);

    while(ans.sz>mx+1) ans.pop_back();

    return ans;


}

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

prison.cpp: In function 'll go(ll)':
prison.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

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