oj.uz

Submission #369932

# Submission time Handle Problem Language Result Execution time Memory
369932 2021-02-22T19:00:31 Z azberjibiou Naan (JOI19_naan) C++17
29 / 100
 539 ms 262148 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 74 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 71 ms 640 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 2 ms 492 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 74 ms 364 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 1 ms 492 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 2 ms 492 KB Output is correct
34 Correct 71 ms 640 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 2 ms 492 KB Output is correct
37 Correct 1 ms 492 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 364 KB Output is correct
40 Correct 2 ms 512 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 1 ms 364 KB Output is correct
43 Runtime error 539 ms 262148 KB Execution killed with signal 9
44 Halted 0 ms 0 KB -