oj.uz

Submission #495124

# Submission time Handle Problem Language Result Execution time Memory
495124 2021-12-18T05:05:19 Z Ziel Gift (IZhO18_nicegift) C++17
18 / 100
 2000 ms 205408 KB 
/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");

#define int ll

const int N = 2e6 + 4;

ll n, k, a[N];

struct node {
	int mx, pos, mx2, pos2;
} t[4 * N];
node merge(node x, node y) {
	if (x.mx > y.mx) {
		if (x.mx2 > y.mx)
			return x;
		else
			return {x.mx, x.pos, y.mx, y.pos};
	}
	if (y.mx2 > x.mx)
		return y;
	return {y.mx, y.pos, x.mx, x.pos};
}
void build(int x = 0, int lx = 1, int rx = n + 1) {
	if (rx - lx == 1) {
		t[x].mx = a[lx];
		t[x].pos = lx;
		t[x].mx2 = -1;
		t[x].pos2 = -1;
	} else {
		int mid = (lx + rx) / 2;
		build(2 * x + 1, lx, mid);
		build(2 * x + 2, mid, rx);
		t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
}
node get(int l, int r, int x = 0, int lx = 1, int rx = n + 1) {
	if (rx <= l || r <= lx) return {-1, -1, -1, -1};
	if (l <= lx && rx <= r) return t[x];
	int mid = (lx + rx) / 2;
	node s1 = get(l, r, 2 * x + 1, lx, mid);
	node s2 = get(l, r, 2 * x + 2, mid, rx);
	return merge(s1, s2);
}
void upd(int i, int v, int x = 0, int lx = 1, int rx = n + 1) {
	if (rx - lx == 1) {
		t[x].mx += v;
		t[x].mx2 = -1;
		t[x].pos = lx;
		t[x].pos2 = -1;
	} else {
		int mid = (lx + rx) / 2;
		if (i < mid)
			upd(i, v, 2 * x + 1, lx, mid);
		else
			upd(i, v, 2 * x + 2, mid, rx);
		t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
}

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
    }
    build();

    vector<pair<int, int>> v;
    while (true) {
    	node cur = get(1, n + 1);
    	if (cur.mx == 0 && cur.mx2 == 0) {
    		cout << sz(v) << '\n';
    		for (int i = 0; i < sz(v); i++)
    			cout << "1 " << v[i].first << ' ' << v[i].second << '\n';
    		return;
    	} else if (cur.mx == 1 && cur.mx2 == 0) {
    		cout << -1;
    		return;
    	}
    	v.push_back({cur.pos, cur.pos2});
    	upd(cur.pos, -1);
    	if (cur.pos2 == -1) {
    		cout << -1;
    		return;
    	}
    	upd(cur.pos2, -1);
    }
}

signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> tt;
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

nicegift.cpp: In function 'void setIO(const string&)':
nicegift.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nicegift.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB n=4
2 Correct 1 ms 332 KB n=3
3 Correct 0 ms 332 KB n=3
4 Correct 0 ms 332 KB n=4
5 Correct 0 ms 332 KB n=4
6 Correct 0 ms 332 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB n=4
2 Correct 1 ms 332 KB n=3
3 Correct 0 ms 332 KB n=3
4 Correct 0 ms 332 KB n=4
5 Correct 0 ms 332 KB n=4
6 Correct 0 ms 332 KB n=2
7 Correct 0 ms 332 KB n=5
8 Correct 2 ms 708 KB n=8
9 Correct 4 ms 712 KB n=14
10 Correct 2 ms 716 KB n=11
11 Correct 27 ms 6548 KB n=50000
12 Correct 24 ms 6452 KB n=50000
13 Correct 12 ms 1484 KB n=10
14 Correct 14 ms 1596 KB n=685
15 Correct 16 ms 1696 KB n=623
16 Correct 8 ms 1168 KB n=973

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB n=4
2 Correct 1 ms 332 KB n=3
3 Correct 0 ms 332 KB n=3
4 Correct 0 ms 332 KB n=4
5 Correct 0 ms 332 KB n=4
6 Correct 0 ms 332 KB n=2
7 Correct 0 ms 332 KB n=5
8 Correct 2 ms 708 KB n=8
9 Correct 4 ms 712 KB n=14
10 Correct 2 ms 716 KB n=11
11 Correct 27 ms 6548 KB n=50000
12 Correct 24 ms 6452 KB n=50000
13 Correct 12 ms 1484 KB n=10
14 Correct 14 ms 1596 KB n=685
15 Correct 16 ms 1696 KB n=623
16 Correct 8 ms 1168 KB n=973
17 Incorrect 18 ms 1728 KB Taken too much stones from the heap
18 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 205408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB n=4
2 Correct 1 ms 332 KB n=3
3 Correct 0 ms 332 KB n=3
4 Correct 0 ms 332 KB n=4
5 Correct 0 ms 332 KB n=4
6 Correct 0 ms 332 KB n=2
7 Correct 0 ms 332 KB n=5
8 Correct 2 ms 708 KB n=8
9 Correct 4 ms 712 KB n=14
10 Correct 2 ms 716 KB n=11
11 Correct 27 ms 6548 KB n=50000
12 Correct 24 ms 6452 KB n=50000
13 Correct 12 ms 1484 KB n=10
14 Correct 14 ms 1596 KB n=685
15 Correct 16 ms 1696 KB n=623
16 Correct 8 ms 1168 KB n=973
17 Incorrect 18 ms 1728 KB Taken too much stones from the heap
18 Halted 0 ms 0 KB -