제출 #545430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545430		nishkarsh	Matching (CEOI11_mat)	C++14	100 / 100	674 ms	40040 KiB

mat

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 1e6+10;
const int mod = 1e9+7;
int Z_func[upperlimit];
int arr[upperlimit];
int fenwick[upperlimit];
int a[upperlimit];
struct indval{
	int ind,val;
};
bool cmp1(indval a,indval b){
	return(a.val<b.val);
}
bool cmp2(indval a,indval b){
	return(a.ind<b.ind);
}
indval b[upperlimit];
int N=upperlimit-1;
int lsb(int pos){
	return (pos&(-pos));
}
void update(int pos,int val){
	while(pos <= N){
		fenwick[pos]+=val;
		pos+=lsb(pos);
	}
}
int query(int pos){
	int ans=0;
	while(pos>0){
		ans+=fenwick[pos];
		pos-=lsb(pos);
	}
	return ans;
}
int main(){
	int n,m,x;
	sd(n);sd(m);
	for(int i = 1; i <= n; i++){
		sd(x);
		a[x]=i;
	}
	for(int i = 1; i <= m; i++){
		sd(b[i].val);
		b[i].ind=i;
	}
	sort(b+1,b+m+1,cmp1);
	for(int i = 1; i <= m; i++) b[i].val=i;
	sort(b+1,b+m+1,cmp2);
	int cur=0,p=2,curr_value;
	Z_func[1]=0;
	N=max(n,m);
	for(int i = 1; i <= n; i++){
		update(a[i],1);
		arr[i] = query(a[i]);
//		cout << arr[i] << " ";
	}
	for(int i = 1; i <= n; i++) update(a[i],-1);
	for(int i = 2; i <= n; i++){
		update(a[i],1);
		curr_value = query(a[i]);
		while(curr_value!=arr[cur+1]){
			if(cur==0) break;
			cur = Z_func[cur];
			while(p < i-cur){
				update(a[p],-1);
				p++;
			}
			curr_value = query(a[i]);
		}
		if(arr[cur+1]==curr_value) cur++;
		Z_func[i]=cur;
	}
	while(p<=n){
		update(a[p],-1);
		p++;
	}
	arr[n+1]=0;
	cur=0;
	p=1;
	int cnt = 0;
	vi ans;
	for(int i = 1; i <= m; i++){
		update(b[i].val,1);
		curr_value = query(b[i].val);
		while(curr_value!=arr[cur+1]){
			if(cur==0) break;
			cur = Z_func[cur];
			while(p < i-cur){
				update(b[p].val,-1);
				p++;
			}
			curr_value = query(b[i].val);
		}
		if(arr[cur+1]==curr_value) cur++;
		if(cur==n){
			cnt++;
			ans.pb(i+1-n);
		}
	}
	pdn(cnt);
	for(int i = 0; i < cnt; i++) pds(ans[i]);
	return 0;
}

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

mat.cpp: In function 'int main()':
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:74:2: note: in expansion of macro 'sd'
   74 |  sd(n);sd(m);
      |  ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:74:8: note: in expansion of macro 'sd'
   74 |  sd(n);sd(m);
      |        ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:76:3: note: in expansion of macro 'sd'
   76 |   sd(x);
      |   ^~
mat.cpp:13:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define sd(x) scanf("%d",&x)
      |               ~~~~~^~~~~~~~~
mat.cpp:80:3: note: in expansion of macro 'sd'
   80 |   sd(b[i].val);
      |   ^~

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