제출 #1205673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205673		simona1230	던전 (IOI21_dungeons)	C++20	컴파일 에러	0 ms	0 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=4*1e5+5;
const int logg=19;
const int base=4;
int n;
vector<int> s,p,w,l,h;
vector<long long> v;
int c,done[maxn];
long long sum[maxn][20][15];
int ver[maxn][20][15];
long long lim[maxn][20][15];

void construct(int x)
{
    //cout<<x<<"! "<<endl;
    for(int i=0; i<n; i++)
    {
        if(v[x]>=s[i])
        {
            ver[i][0][x]=w[i];
            sum[i][0][x]=s[i];
            lim[i][0][x]=1e18;
        }
        else
        {
            ver[i][0][x]=l[i];
            sum[i][0][x]=p[i];
            lim[i][0][x]=s[i];
        }
    }
    ver[n][0][x]=n;
    lim[n][0][x]=1e18;
    for(int j=1; j<=logg; j++)
        for(int i=0; i<=n; i++)
        {
            sum[i][j][x]=sum[i][j-1][x]+sum[ver[i][j-1][x]][j-1][x];
            if(1e18-sum[i][j-1][x]<sum[ver[i][j-1][x]][j-1][x])sum[i][j][x]=1e18;
            ver[i][j][x]=ver[ver[i][j-1][x]][j-1][x];
            long long here=lim[ver[i][j-1][x]][j-1][x]-sum[i][j-1][x];
            if(lim[ver[i][j-1][x]][j-1][x]==1e18)here=1e18;
            lim[i][j][x]=min(lim[i][j-1][x],here);
            //cout<<i<<" "<<j<<" "<<x<<" "<<ver[i][j][x]<<" "<<sum[i][j][x]<<" "<<lim[i][j][x]<<endl;
        }
}

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
    n=N;
    s=S;
    p=P;
    w=W;
    l=L;

    int pw=1;
    v={1};
    while(pw*base<=1e7)
    {
        pw*=base;
        v.push_back(pw);
    }
    v.push_back(1e18);

    for(int i=0;i<v.size();i++)
        construct(i);

    return;
}

long long simulate(int x, int zz)
{
    long long z=zz;
    long long num=0;

    int in=0;
    while(num<v.size()&&x!=n)
    {
        in++;
        if(in>50)return 0;
        while(num+1<v.size()&&z>=v[num+1])num++;
        //cout<<x<<" - "<<z<<" "<<num<<endl;

        for(int j=logg;j>=0;j--)
        {
            //cout<<x<<" "<<j<<" "<<num<<" "<<lim[x][j][num]<<endl;
            if(z<lim[x][j][num])
            {
                z+=sum[x][j][num];
                x=ver[x][j][num];
            }
        }
        //cout<<x<<" "<<x<<endl;
        if(x==n)return z;
        z+=s[x];
        x=w[x];
    }

    return z;
}


/*int main()
{
    while(1)
    {
        int nn=100;
        vector<int> ss,pp,ww,ll;
        int r=1e7;
        for(int i=0;i<nn;i++)
            ss.push_back(r);
        for(int i=0;i<nn;i++)
            pp.push_back(rand()%10);
        for(int i=0;i<nn;i++)
            ww.push_back(min(nn,rand()%2+1+i));
        for(int i=0;i<nn;i++)
            ll.push_back(rand()%(nn+1));
        init(nn,ss,pp,ww,ll);
        cout<<nn<<" "<<5<<endl;
        for(int i=0;i<ss.size();i++)
            cout<<ss[i]<<" ";
        cout<<endl;
        for(int i=0;i<pp.size();i++)
            cout<<pp[i]<<" ";
        cout<<endl;
        for(int i=0;i<ww.size();i++)
            cout<<ww[i]<<" ";
        cout<<endl;
        for(int i=0;i<ll.size();i++)
            cout<<ll[i]<<" ";
        cout<<endl;
        for(int i=1;i<=5;i++)
        {
            int xx,zz;
            xx=rand()%nn;
            zz=rand()%10;
            cout<<xx<<" "<<zz<<endl;
            cout<<simulate(xx,zz)<<endl;
        }
    }
}*/

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

/tmp/ccKnHwaE.o: in function `main':
grader.cpp:(.text.startup+0x15e): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x165): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x183): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x18a): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x196): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x19d): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x1ac): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x1b3): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x1bf): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x1c6): relocation truncated to fit: R_X86_64_PC32 against `.bss'
grader.cpp:(.text.startup+0x1d2): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status