Submission #1070525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070525		_8_8_	Xylophone (JOI18_xylophone)	C++17	47 / 100	85 ms	98640 KiB

xylophone

    #include "xylophone.h"
    #include <bits/stdc++.h>
    using namespace std;
    int p[5002],a[5002],mem[5002][5002];
    int QQ(int l,int r) {
    	if(mem[l][r] != -1) {
    		return mem[l][r];
    	}
    	return mem[l][r] = query(l,r);
    }
    int n_;
    bool bad(int x) {
    	return (x < 1 || x > n_ || p[x]);
    }
    void make(int v,int val) {
    	a[v] = val;
    	p[val] = v;
    }
    void solve(int n) {
    	n_ = n;
    	memset(mem,-1,sizeof(mem));
    	memset(p,0,sizeof(p));
    	memset(a,0,sizeof(a));
    	int nd = n - 1;
    	int l = 1,r = n;
    	while(r - l > 1) {
    		int mid = (l + r) >> 1;
    		if(QQ(1,mid) == nd) {
    			r = mid;
    		} else {
    			l = mid;
    		}
    	}
    	p[n] = r;
    	l = 1,r = p[n];
    	while(r - l > 1) {
    		int mid = (l + r) >> 1;
    		if(QQ(mid,p[n]) == nd) {
    			l = mid;
    		} else {
    			r = mid;
    		}
    	}
    	p[1] = l;
    	a[p[1]] = 1;
    	a[p[n]] = n;
    	int mx = 1;
    	if(p[1] - 1 >= 1) {
    		make(p[1] - 1,1 + QQ(p[1] - 1,p[1]));
    	}
    	for(int i = p[1] - 2;i >= 1;i--) {
    		int t2, t1, val;
    		int t = QQ(i,i + 1);
    		if(bad(a[i + 1] + t))  {
    			val = a[i + 1] - t;
    		} else if(bad(a[i + 1] - t)) {
    			val = a[i + 1] + t;
    		}
    		else {
    			t2 = QQ(i,i + 2);
    			if(a[i + 2] > a[i + 1]) {
    				if(t2 == a[i + 2] - (a[i + 1] - t)) {
    					val = a[i + 1] - t;
    				} else {
    					val = a[i + 1] + t;
    				}
    			} else {
    				if(t2 == a[i + 1] + t - a[i + 2]) {
    					val = a[i + 1] + t;
    				} else {
    					val = a[i + 1] - t;
    				}
    			}
    		}
    		// cout << i << ' ' << val << ' ' << (a[i + 2] > a[i + 1]) << '\n';
    		p[val] = i;
    		a[i] = val;
    	}
    	mx = 1;
    	if(p[1] + 1 < p[n]) {
    		make(p[1] + 1,1 + QQ(p[1],p[1]+1));
    	}
    	for(int i = p[1] + 2;i < p[n];i++) {
    		int val;
    		int t2, t1;
    		int t = QQ(i - 1,i);
    		if(bad(a[i - 1] + t))  {
    			val = a[i - 1] - t;
    		} else if(bad(a[i - 1] - t)) {
    			val = a[i - 1] + t;
    		} else{
    			t2 = QQ(i - 2,i);
    			if(a[i - 2] > a[i - 1]) {
    				if(t2 == a[i - 2] - (a[i - 1] - t)) {
    					val = a[i - 1] - t;
    				} else {
    					val = a[i - 1] + t;
    				}
    			} else {
    				if(t2 == a[i - 1] + t - a[i - 2]) {
    					val = a[i - 1] + t;
    				} else {
    					val = a[i - 1] - t;
    				}
    			}
    		}
    		// cout << i << ' ' << val << '\n';
    		p[val] = i;
    		a[i] = val;
    	}
    	int mn = n;
    	for(int i = p[n] + 1;i <= n;i++) {
    		int val, T = QQ(p[n],i);
    		if(T != n - mn) {
    			mn = val = n - T;
    		} else {
    			int t2, t1;
    			int t = QQ(i - 1,i);
    			if(bad(a[i - 1] + t))  {
    				val = a[i - 1] - t;
    			} else if(bad(a[i - 1] - t)) {
    				val = a[i - 1] + t;
    			} else{
    				t2 = QQ(i - 2,i);
    				if(a[i - 2] > a[i - 1]) {
    					if(t2 == a[i - 2] - (a[i - 1] - t)) {
    						val = a[i - 1] - t;
    					} else {
    						val = a[i - 1] + t;
    					}
    				} else {
    					if(t2 == a[i - 1] + t - a[i - 2]) {
    						val = a[i - 1] + t;
    					} else {
    						val = a[i - 1] - t;
    					}
    				}
    			}
    		}
    		p[val] = i;
    		a[i] = val;
    	}
    	for(int i = 1;i <= n;i++) {
    		answer(p[i],i);
    	}
    }

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:52:15: warning: unused variable 't1' [-Wunused-variable]
   52 |       int t2, t1, val;
      |               ^~
xylophone.cpp:85:15: warning: unused variable 't1' [-Wunused-variable]
   85 |       int t2, t1;
      |               ^~
xylophone.cpp:117:16: warning: unused variable 't1' [-Wunused-variable]
  117 |        int t2, t1;
      |                ^~
xylophone.cpp:47:10: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   47 |      int mx = 1;
      |          ^~

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 0 / 53