Submission #965315

#	Time	Username	Problem	Language	Result	Execution time	Memory
965315		AdamGS	Painting Squares (IOI20_squares)	C++17	100 / 100	153 ms	932 KiB

squares

#include "squares.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int K=10;
int akt[1<<(K-1)];
vector<int>S;
void DFS(int x) {
  while(akt[x]<2) {
    int p=akt[x]; ++akt[x];
    DFS((2*x+p)%(1<<(K-1)));
    S.pb(p);
  }
}
void generuj() {
  S.clear();
  rep(i, 1<<(K-1)) akt[i]=0;
  DFS(0);
  rep(i, (K-1)) S.pb(0);
}
vector<int>paint(int n) {
  generuj();
  while(S.size()>n) S.pop_back();
  S.pb(K);
  return S;
}
int find_location(int n, vector<int>T) {
  rep(i, T.size()) if(T[i]==-1) return n-i;
  generuj();
  rep(i, S.size()) {
    bool ok=true;
    rep(j, T.size()) if(S[i+j]!=T[j]) {
      ok=false;
      break;
    }
    if(ok) return i;
  }
  return 0;
}

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:28:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   while(S.size()>n) S.pop_back();
      |         ~~~~~~~~^~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
squares.cpp:33:3: note: in expansion of macro 'rep'
   33 |   rep(i, T.size()) if(T[i]==-1) return n-i;
      |   ^~~
squares.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
squares.cpp:35:3: note: in expansion of macro 'rep'
   35 |   rep(i, S.size()) {
      |   ^~~
squares.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
squares.cpp:37:5: note: in expansion of macro 'rep'
   37 |     rep(j, T.size()) if(S[i+j]!=T[j]) {
      |     ^~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55