제출 #1008825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008825		Math4Life2020	9월 (APIO24_september)	C++17	100 / 100	102 ms	14772 KiB

september

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using lll = __int128;
const lll p1 = 144403552893599;
const lll a1 = 981372590237;
const lll p2 = 270969106631203;
const lll a2 = 898374183250;

int solve(int N, int M, vector<int> F, vector<vector<int>> S1) {
	vector<vector<int>> S = S1;
	for (ll i=0;i<M;i++) {
		S[i].push_back(0);
	}
	vector<lll> hsh1,hsh2;
	for (ll i=0;i<M;i++) {
		hsh1.push_back(1);
		hsh2.push_back(1);
	}
	vector<ll> stops;
	stops.push_back(0);
	for (ll i=0;i<N;i++) {
		for (ll j=0;j<M;j++) {
			hsh1[j]=(hsh1[j]*(a1+S[j][i]))%p1;
			hsh2[j]=(hsh2[j]*(a2+S[j][i]))%p2;
		}
		bool split = true;
		for (ll j=0;j<M;j++) {
			split = split && (hsh1[j]==hsh1[0]) && (hsh2[j]==hsh2[0]);
		}
		if (split) {
			stops.push_back(i+1);
			for (ll j=0;j<M;j++) {
				hsh1[j]=1;
				hsh2[j]=1;
			}
		}
	}
	//cout << "nstops: "<<stops.size()-1<<"\n";
	ll kv[N];
	ll kind = 0;
	ll delactive[N];
	for (ll i=0;i<N;i++) {
		delactive[i]=0;
		if (stops[kind+1]<=i) {
			kind++;
		}
		kv[S[0][i]]=kind;
	}
	for (ll i=1;i<N;i++) {
		ll x = kv[i]; ll y = kv[F[i]]; //y: parent of x -> if y before x (y<x), then issues
		if (y<x) {
			delactive[y]++;
			delactive[x]--;
			//cout << "+ at "<<y<<", - at "<<x<<"\n";
		}
	}
	ll nact = 0;
	ll ans = 0;
	for (ll i=0;i<(stops.size()-1);i++) {
		nact += delactive[i];
		if (nact == 0) {
			ans++;
		}
	}
	return (ans-1);
}

컴파일 시 표준 에러 (stderr) 메시지

september.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<std::vector<int> >)':
september.cpp:63:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (ll i=0;i<(stops.size()-1);i++) {
      |              ~^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16