oj.uz

Submission #362326

# Submission time Handle Problem Language Result Execution time Memory
362326 2021-02-02T16:13:47 Z mohamedsobhi777 Restore Array (RMI19_restore) C++14
7 / 100
 14 ms 640 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 14 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 14 ms 492 KB Output is correct
6 Correct 9 ms 364 KB Output is correct
7 Correct 4 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 14 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Incorrect 4 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -