1481C - Fence Painting - CodeForces Solution


brute force constructive algorithms greedy *1600

Please click on ads to support us..

Python Code:

from sys import stdin, stdout
def get_ints(): return map(int, stdin.readline().split())
def PRINT(s): stdout.write(s + '\n')


def logic(n,m,A,B,C):
    differences = [[] for i in range(n)]
    for i in range(n):
        x = B[i]
        if A[i] != x:
            differences[x-1].append(i)
    
    last = C[-1]
    if differences[last-1] != []:
        throw = differences[last-1].pop()
    else:
        throw = -1
        for i in range(n):
            if A[i] == B[i]== last:
                throw = i
                break
        if throw == -1:
            return 'NO'
    C.pop()
    ret = []
    for c in C:
        try:
            ret.append(differences[c-1].pop()+1)
        except:
            ret.append(throw+1)
    for a in differences:
        if a != []:
            return 'NO'

    ret.append(throw+1)
    return 'YES\n' + ' '.join([str(x) for x in ret])

    

for w in range(int(stdin.readline())):
    n,m = get_ints()
    A = [int(x) for x in stdin.readline().split()]
    B = [int(x) for x in stdin.readline().split()]
    C = [int(x) for x in stdin.readline().split()]
    PRINT(logic(n,m,A,B,C))

    

C++ Code:

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

void work()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    vector<int> a(n + 1), b(n + 1), c(m + 1), res(m + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &c[i]);
    
    vector<int> mod[n + 1], st(n + 1);
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        st[b[i]] = true;
        if(a[i] != b[i])
        {
            mod[b[i]].push_back(i);
            cnt++;
        }
    }
    
    if(!st[c[m]])
    {
        puts("NO");
        return;
    }
    
    for(int i = m; i >= 1; i--)
        if(mod[c[i]].size())
        {
            int x = mod[c[i]].back();
            mod[c[i]].pop_back();
            res[i] = x;
            cnt--;
        }
    
    if(cnt)
    {
        puts("NO");
        return;
    }
    
    if(!res[m])
    {
        for(int i = 1; i <= n; i++)
            if(b[i] == c[m])
            {
                res[m] = i;
                break;
            }
    }
    
    for(int i = m - 1; i >= 1; i--)
        if(!res[i])
            res[i] = res[i + 1];
    
    puts("YES");
    for(int i = 1; i <= m; i++) printf("%d ", res[i]);
    puts("");
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) work();
    return 0;
}


Comments

Submit
0 Comments
More Questions

1627B - Not Sitting
1663C - Pōja Verdon
1497A - Meximization
1633B - Minority
688B - Lovely Palindromes
66B - Petya and Countryside
1557B - Moamen and k-subarrays
540A - Combination Lock
1553C - Penalty
1474E - What Is It
1335B - Construct the String
1004B - Sonya and Exhibition
1397A - Juggling Letters
985C - Liebig's Barrels
115A - Party
746B - Decoding
1424G - Years
1663A - Who Tested
1073B - Vasya and Books
195B - After Training
455A - Boredom
1099A - Snowball
1651D - Nearest Excluded Points
599A - Patrick and Shopping
237A - Free Cash
1615B - And It's Non-Zero
1619E - MEX and Increments
34B - Sale
1436A - Reorder
1363C - Game On Leaves