Submission #1215606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215606		alimq	Studentsko (COCI14_studentsko)	C++20	30 / 100	308 ms	412 KiB

studentsko

#include <bits/stdc++.h>
using namespace std;

const int n0=21;
int n,k,a[n0],p[n0];
array<int,2> b[n0];

int main() 
{
    cin >> n >> k;
    if(n>20) {
      return 0;
    }
    for(int i=0; i<n; i++) {
      cin >> a[i];
      b[i]={a[i],i};
    }
    sort(b,b+n);
    for(int i=0; i<n; i++) {
      p[b[i][1]]=i;
      // p - каким по величине является элемент, относительно других (0-й, 1-й, и т.д.)
    }
    int ans=n0;
    for(int i=0; i<(1<<n); i++) {
      // для тех что не в выборке, чекаем что порядок верный
      // все кто в 1 блоке идут до 2 блока, и т.д.
      // как проверить блок - просто поделить p[j] на k
      // 0 - первый блок (0...k-1)
      // 1 - второй блок и т.д.
      // поделить и посмотреть что массив отсортирован
      vector<int> check_if_sorted, t;
      for(int j=0; j<n; j++) {
        if(!(i>>j&1)) {
          check_if_sorted.push_back(p[j]/k);
          t.push_back(p[j]/k);
        }
      }
      sort(begin(t),end(t));
      bool sorted=1;
      for(int j=0; j<(int)t.size(); j++) {
        if(check_if_sorted[j]!=t[j]) {
          sorted=0;
        }
      }
      if(sorted) {
        // тогда, выборка хорошая
        ans=min(ans,__builtin_popcount(i));
      }
    }
    cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10