제출 #1348538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1348538		PieArmy	Naan (JOI19_naan)	C++20	컴파일 에러	0 ms	0 KiB

naan

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll
int n,m;
int sum[2023];
int arr[2023][2023];
int perloc[2023];
pair<int,int>ans[2023];
vector<int>v;

int gcd(int x,int y){
	if(x<y)swap(x,y);
	if(!y)return x;
	return gcd(y,x%y);
}
void print(__int128_t x){
	if(x<0){
		cerr<<"-";
		x=-x;
	}
	if(x>9)print(x/10);
	cerr<<int(x%10);
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
			sum[i]+=arr[i][j];
			arr[i][j]+=arr[i][j-1];
		}
	}
	pair<int,int>pos={0,1};
	for(int j=1;j<=n;j++){
		int opt=0;
		pair<__int128_t,int>nex={m+1,1};
		for(int i=1;i<=n;i++){
			if(ans[i].fr)continue;
			int bas=pos.fr/pos.sc+1;
			int l=bas,r=m;
			while(l<r){
				int mi=(l+r)/2;
				__int128_t o=arr[i][bas]-arr[i][bas-1];
				__int128_t p1=pos.sc-(pos.fr%pos.sc);
				__int128_t p2=pos.sc;
				__int128_t x=arr[i][mi]-arr[i][bas];
				if(__int128_t(o*p1+x*p2)*n>=sum[i]*p2)r=mi;
				else l=mi+1;
			}
			__int128_t x=arr[i][l-1]-arr[i][bas];
			__int128_t p1=pos.sc-(pos.fr%pos.sc),p2=pos.sc;
			__int128_t t=arr[i][l]-arr[i][l-1],o=arr[i][bas]-arr[i][bas-1];
			pair<__int128_t,int>can={sum[i]*p2-x*n*p2-o*n*p1,n*t*p2};
			can.fr+=__int128_t(l-1)*can.sc;
			int g=gcd(can.fr,can.sc);
			can.fr/=g;
			can.sc/=g;
			if(nex.fr*can.sc>can.fr*nex.sc){
				opt=i;
				nex.fr=can.fr;nex.sc=can.sc;
			}
		}
		if(nex.sc>1e9){
			__int128_t x=(nex.fr*1000000000ll)/nex.sc+1;
			assert(x*nex.sc>=nex.fr*1000000000);
			nex.fr=x;
			nex.sc=1e9;
		}
		int g=gcd(nex.fr,nex.sc);
		nex.fr/=g;
		nex.sc/=g;
		if(nex.fr>m*nex.sc){
			while(true)cerr<<"**********";
		}
		pos=ans[opt]=nex;
		v.pb(opt);
	}
	pair<int,int>la={0,1};
	for(int i=1;i<=n;i++){
		pair<int,int>me=ans[v[i-1]];
		int a=la.fr/la.sc+1;
		int b=me.fr/me.sc+1;
		int x=arr[v[i-1]][b-1]-arr[v[i-1]][a];
		int p1=la.sc-(la.fr%la.sc),p2=la.sc;
		int l1=(me.fr%me.sc),l2=me.sc;
		int o=arr[v[i-1]][a]-arr[v[i-1]][a-1],t=arr[v[i-1]][b]-arr[v[i-1]][b-1];
		if((o*p1*l2+x*p2*l2+l1*t*p2)*n<sum[v[i-1]]*p2*l2){
			cerr<<v[i-1]<<" ";
			assert(0);
		}
	}
	int las=v.back();
	//if((ans[las].fr/double(ans[las].sc))>5)cerr<<(ans[las].fr/double(ans[las].sc))<<endl;
	v.pop_back();
	for(int x:v){
		if(ans[x].fr==m&&ans[x].sc==1)break;
		cout<<ans[x].fr<<" "<<ans[x].sc<<endl;
	}
	v.pb(las);
	for(int i=1;i<=n;i++){
		perloc[v[i-1]]=i;
	}
	for(int i=1;i<=n;i++){
		cout<<perloc[i]<<" ";
	}
	cout<<endl;
}#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
#define int ll
int n,m;
int sum[2023];
int arr[2023][2023];
int perloc[2023];
pair<int,int>ans[2023];
vector<int>v;

int gcd(int x,int y){
	if(x<y)swap(x,y);
	if(!y)return x;
	return gcd(y,x%y);
}
void print(__int128_t x){
	if(x<0){
		cerr<<"-";
		x=-x;
	}
	if(x>9)print(x/10);
	cerr<<int(x%10);
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>arr[i][j];
			sum[i]+=arr[i][j];
			arr[i][j]+=arr[i][j-1];
		}
	}
	pair<int,int>pos={0,1};
	for(int j=1;j<=n;j++){
		int opt=0;
		pair<__int128_t,int>nex={m+1,1};
		for(int i=1;i<=n;i++){
			if(ans[i].fr)continue;
			int bas=pos.fr/pos.sc+1;
			int l=bas,r=m;
			while(l<r){
				int mi=(l+r)/2;
				__int128_t o=arr[i][bas]-arr[i][bas-1];
				__int128_t p1=pos.sc-(pos.fr%pos.sc);
				__int128_t p2=pos.sc;
				__int128_t x=arr[i][mi]-arr[i][bas];
				if(__int128_t(o*p1+x*p2)*n>=sum[i]*p2)r=mi;
				else l=mi+1;
			}
			__int128_t x=arr[i][l-1]-arr[i][bas];
			__int128_t p1=pos.sc-(pos.fr%pos.sc),p2=pos.sc;
			__int128_t t=arr[i][l]-arr[i][l-1],o=arr[i][bas]-arr[i][bas-1];
			pair<__int128_t,int>can={sum[i]*p2-x*n*p2-o*n*p1,n*t*p2};
			can.fr+=__int128_t(l-1)*can.sc;
			int g=gcd(can.fr,can.sc);
			can.fr/=g;
			can.sc/=g;
			if(nex.fr*can.sc>can.fr*nex.sc){
				opt=i;
				nex.fr=can.fr;nex.sc=can.sc;
			}
		}
		if(nex.sc>1e9){
			__int128_t x=(nex.fr*1000000000ll)/nex.sc+1;
			assert(x*nex.sc>=nex.fr*1000000000);
			nex.fr=x;
			nex.sc=1e9;
		}
		int g=gcd(nex.fr,nex.sc);
		nex.fr/=g;
		nex.sc/=g;
		if(nex.fr>m*nex.sc){
			while(true)cerr<<"**********";
		}
		pos=ans[opt]=nex;
		v.pb(opt);
	}
	pair<int,int>la={0,1};
	for(int i=1;i<=n;i++){
		pair<int,int>me=ans[v[i-1]];
		int a=la.fr/la.sc+1;
		int b=me.fr/me.sc+1;
		int x=arr[v[i-1]][b-1]-arr[v[i-1]][a];
		int p1=la.sc-(la.fr%la.sc),p2=la.sc;
		int l1=(me.fr%me.sc),l2=me.sc;
		int o=arr[v[i-1]][a]-arr[v[i-1]][a-1],t=arr[v[i-1]][b]-arr[v[i-1]][b-1];
		if((o*p1*l2+x*p2*l2+l1*t*p2)*n<sum[v[i-1]]*p2*l2){
			cerr<<v[i-1]<<" ";
			assert(0);
		}
	}
	int las=v.back();
	//if((ans[las].fr/double(ans[las].sc))>5)cerr<<(ans[las].fr/double(ans[las].sc))<<endl;
	v.pop_back();
	for(int x:v){
		if(ans[x].fr==m&&ans[x].sc==1)break;
		cout<<ans[x].fr<<" "<<ans[x].sc<<endl;
	}
	v.pb(las);
	for(int i=1;i<=n;i++){
		perloc[v[i-1]]=i;
	}
	for(int i=1;i<=n;i++){
		cout<<perloc[i]<<" ";
	}
	cout<<endl;
}

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

naan.cpp:115:2: error: stray '#' in program
  115 | }#include<bits/stdc++.h>
      |  ^
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:11: error: 'bits' was not declared in this scope
  115 | }#include<bits/stdc++.h>
      |           ^~~~
naan.cpp:115:16: error: 'stdc' was not declared in this scope; did you mean 'std'?
  115 | }#include<bits/stdc++.h>
      |                ^~~~
      |                std
naan.cpp:115:3: error: 'include' does not name a type
  115 | }#include<bits/stdc++.h>
      |   ^~~~~~~
naan.cpp:124:5: error: redefinition of 'll n'
  124 | int n,m;
      |     ^
naan.cpp:10:5: note: 'll n' previously declared here
   10 | int n,m;
      |     ^
naan.cpp:124:7: error: redefinition of 'll m'
  124 | int n,m;
      |       ^
naan.cpp:10:7: note: 'll m' previously declared here
   10 | int n,m;
      |       ^
naan.cpp:125:5: error: redefinition of 'll sum [2023]'
  125 | int sum[2023];
      |     ^~~
naan.cpp:11:5: note: 'll sum [2023]' previously declared here
   11 | int sum[2023];
      |     ^~~
naan.cpp:126:5: error: redefinition of 'll arr [2023][2023]'
  126 | int arr[2023][2023];
      |     ^~~
naan.cpp:12:5: note: 'll arr [2023][2023]' previously declared here
   12 | int arr[2023][2023];
      |     ^~~
naan.cpp:127:5: error: redefinition of 'll perloc [2023]'
  127 | int perloc[2023];
      |     ^~~~~~
naan.cpp:13:5: note: 'll perloc [2023]' previously declared here
   13 | int perloc[2023];
      |     ^~~~~~
naan.cpp:128:14: error: redefinition of 'std::pair<long long int, long long int> ans [2023]'
  128 | pair<int,int>ans[2023];
      |              ^~~
naan.cpp:14:14: note: 'std::pair<long long int, long long int> ans [2023]' previously defined here
   14 | pair<int,int>ans[2023];
      |              ^~~
naan.cpp:129:12: error: redefinition of 'std::vector<long long int> v'
  129 | vector<int>v;
      |            ^
naan.cpp:15:12: note: 'std::vector<long long int> v' previously defined here
   15 | vector<int>v;
      |            ^
naan.cpp:131:5: error: redefinition of 'll gcd(ll, ll)'
  131 | int gcd(int x,int y){
      |     ^~~
naan.cpp:17:5: note: 'll gcd(ll, ll)' previously defined here
   17 | int gcd(int x,int y){
      |     ^~~
naan.cpp:136:6: error: redefinition of 'void print(__int128)'
  136 | void print(__int128_t x){
      |      ^~~~~
naan.cpp:22:6: note: 'void print(__int128)' previously defined here
   22 | void print(__int128_t x){
      |      ^~~~~
naan.cpp:145:8: error: redefinition of 'int main()'
  145 | signed main(){
      |        ^~~~
naan.cpp:31:8: note: 'int main()' previously defined here
   31 | signed main(){
      |        ^~~~