oj.uz

Submission #891280

# Submission time Handle Problem Language Result Execution time Memory
891280 2023-12-22T16:18:04 Z fanwen RMQ (NOI17_rmq) C++17
23 / 100
 633 ms 600 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define file(name)                  \
    if(fopen(name".inp", "r"))      \
        freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout); 

const int MAX = 1e5 + 5;

int n, q, ans[MAX];

vector <tuple <int, int, int>> queries;

namespace sub1 {
	bool check() {
		return max(n, q) <= 10;
	}

	template<class T, T (*merge) (T, T)> 
	struct sparse_table {
	    vector <vector <T>> q;
	    int n;
	
	    sparse_table() {}
	    sparse_table(const vector <T> &v) : n((int) v.size()) {
	        q.push_back(v);
	        for (int k = 1; (1 << k) <= n; ++k) {
	            q.emplace_back(n - (1 << k) + 1);
	            for (int i = 0; i + (1 << k) <= n; ++i) {
	                q[k][i] = merge(q[k - 1][i], q[k - 1][i + (1 << (k - 1))]);
	            }
	        }
	    }
	
	    T get(int l, int r) {
	        assert(0 <= l && l <= r && r < n);
	        int k = 31 - __builtin_clz(r - l + 1);
	        return merge(q[k][l], q[k][r - (1 << k) + 1]);
	    }
	};

	int op (int a, int b) {
		return min(a, b);
	}

	void solve() {
		vector <int> a(n);
		iota(a.begin(), a.end(), 0);
		do {
			sparse_table <int, op> rmq(a);
			bool oke = true;
			for (tuple <int, int, int> tmp : queries) {
				int l, r, mi; tie(l, r, mi) = tmp;
				oke &= rmq.get(l, r) == mi;
			}
			if(oke) {
				for (int i = 0; i < n; ++i) cout << a[i] << " ";
				exit(0);
			}
		} while(next_permutation(a.begin(), a.end()));

		for (int i = 0; i < n; ++i) cout << -1 << " "; exit(0);
	}
}

void you_make_it(void) {
	cin >> n >> q;
	for (int i = 0; i < q; ++i) { 
		int l, r, mi; cin >> l >> r >> mi;
		queries.emplace_back(l, r, mi);
	}	

	if(sub1::check()) sub1::solve();
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("rmq");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

rmq.cpp: In function 'void sub1::solve()':
rmq.cpp:66:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   66 |   for (int i = 0; i < n; ++i) cout << -1 << " "; exit(0);
      |   ^~~
rmq.cpp:66:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   66 |   for (int i = 0; i < n; ++i) cout << -1 << " "; exit(0);
      |                                                  ^~~~
rmq.cpp: In function 'int main()':
rmq.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
rmq.cpp:86:5: note: in expansion of macro 'file'
   86 |     file("rmq");
      |     ^~~~
rmq.cpp:10:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
rmq.cpp:86:5: note: in expansion of macro 'file'
   86 |     file("rmq");
      |     ^~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 80 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 627 ms 456 KB Output is correct
7 Correct 59 ms 344 KB Output is correct
8 Correct 633 ms 440 KB Output is correct
9 Correct 64 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 80 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 627 ms 456 KB Output is correct
7 Correct 59 ms 344 KB Output is correct
8 Correct 633 ms 440 KB Output is correct
9 Correct 64 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 80 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 460 KB Output is correct
6 Correct 627 ms 456 KB Output is correct
7 Correct 59 ms 344 KB Output is correct
8 Correct 633 ms 440 KB Output is correct
9 Correct 64 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -