oj.uz

Submission #922527

# Submission time Handle Problem Language Result Execution time Memory
922527 2024-02-05T16:06:54 Z salmon Painting Walls (APIO20_paint) C++14
0 / 100
 2 ms 8536 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

set<int> lst[100100];
vector<int> pos[50100];
vector<int> contract[100100];
bool can[100100];
bool l[100100];

int minimumInstructions(int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {



    for(int i = 0; i < N; i++){
        pos[C[i]].push_back(i);
        can[i] = false;
    }

    for(int i = 0; i < M; i++){
        for(int j : B[i]){
            for(int k : pos[j]){
                contract[k].push_back(i);
            }
        }
    }

    vector<int> v;

    for(int i = 0; i < N; i++){
        int it = 0;
        int it1 = 0;

        vector<int> temp;
        if(contract[i].size() != 0 && contract[i][0] == 0) temp.push_back(0);

        while(it < v.size() && it1 < contract[i].size()){
            if(v[it] + 1 == contract[i][it1]){
                if(v[it] != M - 1) temp.push_back(v[it] + 1);
                else{
                    can[i] = true;
                }
            }

            if(v[it] + 1 <= contract[i][it1]){
                it++;
            }
            else{
                it1++;
            }
        }
    }
    for(int i = N; i < N * 2 - 1; i++){
        int it = 0;
        int it1 = 0;

        vector<int> temp;
        if(contract[i % N].size() != 0 && contract[i % N][0] == 0) temp.push_back(0);

        while(it < v.size() && it1 < contract[i % N].size()){
            if(v[it] + 1 == contract[i % N][it1]){
                if(v[it] != M - 1) temp.push_back(v[it] + 1);
                else{
                    can[i % N] = true;
                }
            }

            if(v[it] + 1 <= contract[i % N][it1]){
                it++;
            }
            else{
                it1++;
            }
        }
    }


    vector<int> start;

    for(int i = 0; i < M; i++){
        if(can[i]) start.push_back(i);
    }

    for(int i = 0; i < N; i++){
        if(can[i + M - 1 % N]) l[i] = true;
        else l[i] = false;
    }

    if(start.size() == 0){
        return -1;
    }

    int ans = 1100100100;

    for(int i : start){
        int cont = 1;
        int r = i;
        int go = i - M + N;
        int it = 0;
        int take = 0;

        while(r < go){
            cont++;
            take = r;
            while(it < r){
                it++;
                if(can[i]){
                    take = i + M - 1;
                }
            }

            if(take == r){
                cont = 1100100100;
                break;
            }
            r = take;
        }

        ans = min(ans,cont);
    }

    if(ans == 1100100100) return -1;

    return ans;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(it < v.size() && it1 < contract[i].size()){
      |               ~~~^~~~~~~~~~
paint.cpp:38:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(it < v.size() && it1 < contract[i].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while(it < v.size() && it1 < contract[i % N].size()){
      |               ~~~^~~~~~~~~~
paint.cpp:61:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while(it < v.size() && it1 < contract[i % N].size()){
      |                                ~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -