oj.uz

답안 #616160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
616160 2022-08-01T01:05:44 Z rrrr10000 고대 책들 (IOI17_books) C++14
42 / 100
 2000 ms 16344 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.bein())
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
long long minimum_walk1(std::vector<int> p, int s) {
	ll l=0,r=p.size()-1;
	while(l<s&&p[l]==l)l++;
	while(r>s&&p[r]==r)r--;
	vi v;
	REP(i,l,r+1)v.pb(p[i]-l);
	s-=l;
	ll n=v.size(),ans=0;
	rep(i,n-1){
		ll c=0;
		rep(j,i+1)if(v[j]>i)c++;
		if(c==0)c++;
		ans+=c;
	}
	return ans*2;
}
long long minimum_walk(std::vector<int> p, int s) {
	ll l=0,r=p.size()-1;
	while(l<s&&p[l]==l)l++;
	while(r>s&&p[r]==r)r--;
	vi v;
	REP(i,l,r+1)v.pb(p[i]-l);
	s-=l;
	ll n=v.size(),ans=0;
	rep(i,n-1){
		rep(j,i+1)if(v[j]>i)ans++;
	}
	vvi dp(n,vi(n,inf));
	dp[s][s]=0;
	for(ll l=s;l>=0;l--){
		ll mi=inf,ma=-inf;
		REP(r,l,n){
			chmax(ma,v[r]);
			chmin(mi,v[r]);
			if(l)chmin(dp[l-1][r],dp[l][r]+1);
			if(r!=n-1)chmin(dp[l][r+1],dp[l][r]+1);
			chmin(dp[min(l,mi)][max(r,ma)],dp[l][r]);
		}
	}
	return (ans+dp[0][n-1])*2;
}
void check(ll n,ll s){
	map<vi,ll> dp;
	vi tmp(n+1);rep(i,n)tmp[i]=i;
	tmp[n]=n;
	tmp.pb(s);
	dp[tmp]=0;
	deque<vi> deq;
	deq.pb(tmp);
	ll cnt=0;
	while(!deq.empty()){
		auto t=deq.front();deq.pop_front();
		vi nex=t;
		swap(nex[n],nex[nex.back()]);
		if(!dp.count(nex)){
			dp[nex]=dp[t];deq.push_front(nex);
		}
		nex=t;
		if(nex.back()!=n-1)nex.back()++;
		if(!dp.count(nex)){
			dp[nex]=dp[t]+1;deq.pb(nex);
		}
		nex=t;
		if(nex.back()!=0)nex.back()--;
		if(!dp.count(nex)){
			dp[nex]=dp[t]+1;deq.pb(nex);
		}
	}
	for(auto x:dp)if(x.fi[n+1]==s&&x.fi[n]==n){
		vector<int> p;
		rep(i,n)p.pb(x.fi[i]);
		if(minimum_walk(p,s)!=x.se){
			outv(p);
			out(s);
			out(minimum_walk(p,s));
			out(x.se);
			return;
		}
	}
}
/*
int main(){
	rep(tt,100000){
		ll n=rand()%7+1;
		out(n);
		vector<int> p(n);rep(i,n)p[i]=i;
		random_shuffle(all(p));
		ll r1=minimum_walk_g(p,0);
		ll r2=minimum_walk(p,0);
		if(r1!=r2){
			out(tt);
			outv(p);
			out(r1);out(r2);
			break;
		}
	}
	// REP(n,1,9)rep(s,n)check(n,s);
}
*/

Compilation message

books.cpp: In function 'void check(ll, ll)':
books.cpp:72:5: warning: unused variable 'cnt' [-Wunused-variable]
   72 |  ll cnt=0;
      |     ^~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 4 ms 8072 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8020 KB Output is correct
24 Correct 4 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Correct 4 ms 8148 KB Output is correct
27 Correct 4 ms 8148 KB Output is correct
28 Correct 6 ms 8148 KB Output is correct
29 Correct 5 ms 8148 KB Output is correct

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 4 ms 8072 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8020 KB Output is correct
24 Correct 4 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Correct 4 ms 8148 KB Output is correct
27 Correct 4 ms 8148 KB Output is correct
28 Correct 6 ms 8148 KB Output is correct
29 Correct 5 ms 8148 KB Output is correct
30 Execution timed out 2080 ms 16344 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8148 KB Output is correct
3 Correct 6 ms 8108 KB Output is correct
4 Correct 6 ms 8020 KB Output is correct
5 Correct 6 ms 8148 KB Output is correct
6 Correct 5 ms 8108 KB Output is correct
7 Correct 6 ms 8148 KB Output is correct
8 Correct 5 ms 8112 KB Output is correct
9 Correct 7 ms 8148 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 5 ms 8108 KB Output is correct
12 Correct 5 ms 8200 KB Output is correct
13 Correct 6 ms 8148 KB Output is correct
14 Correct 7 ms 8112 KB Output is correct
15 Correct 6 ms 8148 KB Output is correct
16 Correct 5 ms 8140 KB Output is correct
17 Correct 6 ms 8148 KB Output is correct
18 Correct 6 ms 8148 KB Output is correct
19 Correct 6 ms 8148 KB Output is correct
20 Correct 6 ms 8132 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 4 ms 8072 KB Output is correct
20 Correct 4 ms 8148 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8020 KB Output is correct
24 Correct 4 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Correct 4 ms 8148 KB Output is correct
27 Correct 4 ms 8148 KB Output is correct
28 Correct 6 ms 8148 KB Output is correct
29 Correct 5 ms 8148 KB Output is correct
30 Execution timed out 2080 ms 16344 KB Time limit exceeded
31 Halted 0 ms 0 KB -