oj.uz

Submission #639619

# Submission time Handle Problem Language Result Execution time Memory
639619 2022-09-10T18:19:48 Z Pietra Karte (COCI18_karte) C++14
36 / 120
 1000 ms 2404 KB 
#include<bits/stdc++.h>
using namespace std ;
// o ideal eh começar decrescente
// o ideal eh o começo ter os certos
// se quiser mudar

const int maxn = 1e5 + 5 ;

int n, k, v[maxn], ct[maxn], used[maxn], seq[maxn] ;

// pga o menorr q satisfaz smp pros verdadeiros
// pros falos coloca os maiores mais a esq
int main(){

    cin >> n >> k ;

    for(int i = 0 ; i < n ; i++) cin >> v[i] ;

    bool ans = 0 ;

    for(int mask = 0 ; mask < (1<<n) ; mask++){ // 0 = falso
        int ctr = 0, on = 0 ;
        for(int i = n - 1 ; i >= 0 ; i--){
            ct[i] = ctr ;
            if(!(mask&(1<<i))) ctr++, on++ ;
        }
        for(int i = 0 ; i < n ; i++) used[i] = 0, seq[i] = -1 ;
        for(int i = 0 ; i < n ; i++){ // colocar os vdds
            if(!(mask&(1<<i))) continue ;
            int x = ct[i] ; //preciso do 1o valor menor ou igual a isso q n tenha sido usado
            int mn = maxn, id = -1 ;
            for(int j = 0 ; j < n ; j++){
                if(!used[j]){
                    if(mn > v[j] && v[j] <= x) mn = v[j], id = j ;
                }
            }
            if(id != -1) seq[i] = v[id] ; used[id] = 1 ;
        }
        // colocar os falos - os maiores 1o
        for(int i = 0 ; i < n ; i++){
            if(mask&(1<<i)) continue ;
            int x = ct[i] ;
            int mx = -1, id = -1 ;
            for(int j = 0 ; j < n ; j++){
                if(used[j] || v[j] <= x) continue ;
                if(mx < v[j]) mx = v[j], id = j ;
            }
            if(id != -1) used[id] = 1, seq[i] = v[id] ;
        }
        bool ok = 1 ;
        if(on != k) ok = 0 ;
        for(int i = 0 ; i < n ; i++) if(seq[i] == -1) ok = 0 ;
        if(ok){
            for(int i = 0 ; i < n ; i++) cout << seq[i] << " " ;
            cout << "\n" ;
            exit(0) ;
        }
    }

    cout << "-1\n" ;

}

Compilation message

karte.cpp: In function 'int main()':
karte.cpp:37:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |             if(id != -1) seq[i] = v[id] ; used[id] = 1 ;
      |             ^~
karte.cpp:37:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |             if(id != -1) seq[i] = v[id] ; used[id] = 1 ;
      |                                           ^~~~
karte.cpp:19:10: warning: unused variable 'ans' [-Wunused-variable]
   19 |     bool ans = 0 ;
      |          ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 312 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 42 ms 312 KB Output is correct

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 2404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 1396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 1700 KB Time limit exceeded
2 Halted 0 ms 0 KB -