Submission #851919

#	Time	Username	Problem	Language	Result	Execution time	Memory
851919		serifefedartar	Volontiranje (COCI21_volontiranje)	C++17	0 / 110	1 ms	2396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 1e6 + 5;

vector<int> A;
int pos[MAXN];
int n, vis[MAXN]; 

vector<int> find_LIS() {
	vector<int> LIS;
	for (int i = 1; i <= n; i++) {
		if (vis[i])
			continue;

		int q = upper_bound(LIS.begin(), LIS.end(), A[i]) - LIS.begin();
		if (q == LIS.size())
			LIS.push_back(A[i]);
		LIS[q] = A[i]; 
	}

	return LIS;
}

int main() {
	fast
	cin >> n;

	A = vector<int>(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		pos[A[i]] = i;
	}

	int mx = 0;
	vector<vector<int>> ans;
	for (int i = 1; i <= n; i++) {
		vector<int> LIS = find_LIS();
		if (LIS.size() < mx)
			break;

		mx = max(mx, (int)LIS.size());
		for (auto u : LIS)
			vis[pos[u]] = true;

		ans.push_back({});
		for (auto u : LIS)
			ans.back().push_back(pos[u]);
		sort(ans.back().begin(), ans.back().end()); 
	}

	cout << ans.size() << " " << ans[0].size() << "\n";
	for (auto u : ans) {
		for (auto item : u)
			cout << item << " ";
		cout << "\n"; 
	}
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> find_LIS()':
Main.cpp:23:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if (q == LIS.size())
      |       ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |   if (LIS.size() < mx)
      |       ~~~~~~~~~~~^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 60