제출 #362326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362326		mohamedsobhi777	Restore Array (RMI19_restore)	C++14	7 / 100	14 ms	640 KiB

restore

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n, k;
int L[N], R[N], K[N], V[N];

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n >> k;
       for (int i = 0; i < k; ++i)
       {
              cin >> L[i] >> R[i] >> K[i] >> V[i];
       }

       // just bruteforce

       for (int i = 0; i < (1 << n); ++i)
       {
              bool ok = 1;
              vi ve(n, 0);
              ve[0] = (i & 1);
              for (int j = 1; j < n; ++j)
              {
                     ve[j] = (ve[j - 1] + (!!(i & (1 << j))));
              }
              auto get = [&](int l, int r) -> int {
                     return ve[r] - (l ? ve[l - 1] : 0);
              };
              for (int j = 0; j < k; ++j)
              {
                     int len = R[j] - L[j] + 1;
                     if (V[j] == 0)
                     {
                            if (get(L[j], R[j]) > len - K[j])
                            {
                                   ok = 0;
                                   break;
                            }
                     }
                     else
                     {
                            if (get(L[j], R[j]) <= len - K[j])
                            {
                                   ok = 0;
                                   break;
                            }
                     }
              }

              if (ok)
              {
                     for (int j = 0; j < n; ++j)
                     {
                            cout << !!(i & (1 << j)) << " ";
                     }
                     exit(0);
              }
       }

       cout << -1;
       return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55