oj.uz

Submission #278056

# Submission time Handle Problem Language Result Execution time Memory
278056 2020-08-21T09:25:58 Z erkam Xylophone (JOI18_xylophone) C++17
0 / 100
 3 ms 384 KB 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
#include<set>
#include "xylophone.h"
#include<map>
#define endl "\n"
#define all(v) v.begin(),v.end()
#define st first
#define nd second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long lo;
const int mod=1000000007,N=500005;
lo a,b,c,d,e,f,g=1,h[N];
pair<lo,lo>arr[N];
string s;
vector<lo>v;

// int query(int a,int b){ }
// void answer(int a,int b){ }

void solve(int n){
	for(lo i=1;i<n;i++){
		arr[i].st=query(i,i+1);
		if(i<n-1)arr[i].nd=query(i,i+2);
	}
	h[1]=1;
	for(lo i=1;i<=n-2;i++){
		if(arr[i].st+arr[i+1].st==arr[i].nd)h[i+1]=h[i];
		else h[i+1]=(h[i]^1);
	}
	bool ok=0;
	map<lo,lo>maap;
	lo mx=0,sum=0,mn=0;
	for(lo i=1;i<n;i++){
		if(h[i]==0)sum-=arr[i].st;
		else sum+=arr[i].st;
		if(maap[sum]==1){ok=1; break;}
		maap[sum]++;
		mx=max(sum,mx);
		mn=min(sum,mn);
	}
	if(ok==0 and mx-mn==n-1){
		lo hehe=n-mx;
		answer(1,hehe);
		for(lo i=1;i<n;i++){
			hehe+=arr[i].st*(h[i]==0?-1:1);
			answer(i+1,hehe);
		}
		return;
	}
	h[1]=0;
	sum=0,mx=0;
	for(lo i=1;i<=n-2;i++){
		if(arr[i].st+arr[i+1].st==arr[i].nd)h[i+1]=h[i];
		else h[i+1]=(h[i]^1);
	}
	for(lo i=1;i<n;i++){
		if(h[i]==0)sum-=arr[i].st;
		else sum+=arr[i].st;
		mx=max(sum,mx);
	}
	lo hehe=n-mx;
	answer(1,hehe);
	for(lo i=1;i<n;i++){
		hehe+=arr[i].st*(h[i]==0?-1:1);
		answer(i+1,hehe);
	}

}
 
// int main(){
// 	#ifdef local
// 		freopen("in.txt","r",stdin);
// 		freopen("out.txt","w",stdout);
// 	#endif
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(NULL); cout.tie(NULL);
// 	// cin >> g;
// 	// while(g--)solve();
// }

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 3 ms 384 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 3 ms 384 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 3 ms 384 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -