제출 #369932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369932		azberjibiou	Naan (JOI19_naan)	C++17	29 / 100	539 ms	262148 KiB

naan

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
#define fir first
#define sec second
#define ll long long
#define pii pair<int, int>
const int mxN=2020;
typedef struct frac{
    ll ja, mo;
}frac;
int N, L;
int V[mxN][mxN];
bool Chk[mxN];
vector <vector<int>> v;
vector <int> tmp;
frac ans[mxN];
int sum[mxN];
frac gop(frac a, frac b)
{
    frac res={a.ja*b.ja, a.mo*b.mo};
    if(res.mo<0)    res.mo*=-1, res.ja*=-1;
    return res;
}
frac mnus(frac a, frac b)
{
    frac res={a.ja*b.mo-a.mo*b.ja, a.mo*b.mo};
    if(res.mo<0)    res.mo*=-1, res.ja*=-1;
    return res;
}
frac pls(frac a, frac b)
{
    frac res={a.ja*b.mo+a.mo*b.ja, a.mo*b.mo};
    if(res.mo<0)    res.mo*=-1, res.ja*=-1;
    return res;
}
bool cmp(frac a, frac b)
{
    return mnus(a, b).ja<0;
}
bool ok(int idx, int pos, ll cur)
{
    if(pos==N)
    {
        for(int i=0;i<N-1;i++)   cout << ans[i].ja << " " << ans[i].mo << '\n';
        for(int i=0;i<N;i++)    cout << v[idx][i] << " ";
        return true;
    }
    frac now;
    if(pos==0)  now={0, 1};
    else    now=ans[pos-1];
    ll ncur=cur;
    frac tot={sum[v[idx][pos]], N};
    while(ncur!=L && cmp(gop(mnus({ncur, 1}, now), {V[v[idx][pos]][ncur], 1}), tot))
    {
        //printf("len=%d, %d\n", gop(mnus({ncur, 1}, now), {V[v[idx][pos]][ncur], 1}).ja, gop(mnus({ncur, 1}, now), {V[v[idx][pos]][ncur], 1}).mo);
        tot=mnus(tot, gop(mnus({ncur, 1}, now), {V[v[idx][pos]][ncur], 1}));
        now={ncur, 1};
        ncur++;
    }
 
    if(ncur==L && cmp(gop(mnus({ncur, 1}, now), {V[v[idx][pos]][ncur], 1}), tot))  return false;
    else
    {
        ans[pos]=pls(now, {tot.ja, tot.mo*V[v[idx][pos]][ncur]});
        //printf("ans[%d]=%d, %d\n", pos, ans[pos].ja, ans[pos].mo);
        if(ok(idx, pos+1, ncur))    return true;
    }
    return false;
}
void jag(int pos)
{
    if(pos==N+1)
    {
        v.push_back(tmp);
        return;
    }
    for(int i=1;i<=N;i++)
    {
        if(Chk[i])  continue;
        Chk[i]=true;
        tmp.push_back(i);
        jag(pos+1);
        tmp.pop_back();
        Chk[i]=false;
    }
}
int main()
{
    gibon
    cin >> N >> L;
    for(int i=1;i<=N;i++)   for(int j=1;j<=L;j++)   cin >> V[i][j];
    for(int i=1;i<=N;i++)   for(int j=1;j<=L;j++)   sum[i]+=V[i][j];
    jag(1);
    for(int i=0;i<v.size();i++)
    {
        //printf("i=%d\n", i);
        //for(int j=0;j<N;j++)    printf("%d ", v[i][j]);
        //printf("\n");
        if(ok(i, 0, 1))    return 0;
    }
    cout << -1212;
}

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

naan.cpp: In function 'int main()':
naan.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 0 / 71