oj.uz

Submission #1069516

# Submission time Handle Problem Language Result Execution time Memory
1069516 2024-08-22T04:46:08 Z Malix Beech Tree (IOI23_beechtree) C++17
9 / 100
 45 ms 4296 KB 
#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;

#define REP(a,b,c) for(int a=b;a<c;a++)
#define PB push_back
#define F first
#define S second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;

std::vector<int> beechtree(int n, int m, std::vector<int> p, std::vector<int> c)
{
    if(n<=8){
        vi ans(n,0);
        vii a(n);
        REP(i,0,n)a[i].PB(i);
        for(int i=n-1;i>=1;i--)for(auto u:a[i])a[p[i]].PB(u);
        vii b=a;
        REP(i,0,n){
            int s=a[i].size();
            if(s==1){
                ans[i]=1;
                continue;
            }
            map<int,int> mp;
            bool flag=1;
            REP(j,1,s){
                if(b[i][mp[c[b[i][j]]]]!=p[b[i][j]]){
                    flag=0;
                    break;
                }
                mp[c[b[i][j]]]++;
            }
            if(flag){
                ans[i]=1;
                continue;
            }
            next_permutation(b[i].begin()+1,b[i].end());
            while(b[i]!=a[i]){
                mp.clear();
                flag=1;
                REP(j,1,s){
                    if(b[i][mp[c[b[i][j]]]]!=p[b[i][j]]){
                        flag=0;
                        break;
                    }
                    mp[c[b[i][j]]]++;
                }
                if(flag)break;
                next_permutation(b[i].begin()+1,b[i].end());
            }
            if(flag)ans[i]=1;
        }
        return ans;
    }
    bool flag=1;
    REP(i,1,n)if(p[i]!=i-1)flag=0;
    if(flag){
        vi ans(n,0);
        ans[n-1]=1;
        int k=c[n-1];
        for(int i=n-2;i>=0;i--){
            if(c[i]!=k)break;
            ans[i]=1;
        }
        return ans;
    }
    return {};
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 432 KB 2nd lines differ - expected: 18 tokens, found 0 tokens
3 Halted 0 ms 0 KB -

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 360 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 356 KB Output is correct
34 Correct 1 ms 348 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 45 ms 4296 KB 2nd lines differ - on the 199999th token, expected: '1', found: '0'
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 2nd lines differ - expected: 115 tokens, found 0 tokens
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 45 ms 4296 KB 2nd lines differ - on the 199999th token, expected: '1', found: '0'
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 432 KB 2nd lines differ - expected: 18 tokens, found 0 tokens
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 432 KB 2nd lines differ - expected: 18 tokens, found 0 tokens
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 360 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 1 ms 348 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
26 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 432 KB 2nd lines differ - expected: 18 tokens, found 0 tokens
3 Halted 0 ms 0 KB -