Submission #337395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337395	2020-12-20T14:30:02 Z	ryangohca	Naan (JOI19_naan)	C++17	Compilation error	0 ms	0 KB

naan

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
struct fraction{
    __int128_t num, den;
    fraction(int num=0, int den=1):num(num), den(den){}
 
    void normalize(){
        int g = __gcd(num, den);
        num /= g;
        den /= g;
        if(den < 0){
            num = -num;
            den = -den;
        }
    }
 
    fraction operator-(){
        return fraction{-num, den};
    }
 
    fraction operator+=(const fraction &b){
        num = num*b.den + den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator-=(const fraction &b){
        num = num*b.den - den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator*=(const fraction &b){
        num = num*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator/=(const fraction &b){
        num = num*b.den;
        den = den*b.num;
        normalize();
        return *this;
    }
};
 
fraction operator+(fraction a, const fraction &b){return (a += b);}
fraction operator-(fraction a, const fraction &b){return (a -= b);}
fraction operator*(fraction a, const fraction &b){return (a *= b);}
fraction operator/(fraction a, const fraction &b){return (a /= b);}
bool operator==(const fraction &a, const fraction &b){return 1.0*a.num*b.den == 1.0*a.den*b.num;}
bool operator<(const fraction &a, const fraction &b){return 1.0*a.num*b.den < 1.0*a.den*b.num;}
bool operator>(const fraction &a, const fraction &b){return 1.0*a.num*b.den > 1.0*a.den*b.num;}
bool operator<=(const fraction &a, const fraction &b){return 1.0*a.num*b.den <= 1.0*a.den*b.num;}
bool operator>=(const fraction &a, const fraction &b){return 1.0*a.num*b.den >= 1.0*a.den*b.num;}
 
int nums[2000][2000];
fraction cuts[2000][2000];
vector<fraction> confirmed;
vector<int> order;
bool ordered[2000];
inline int read() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar_unlocked();
	}
	return x;
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n = read(), l = read();
    fraction zero = fraction(0, 1), one = fraction(1, 1);
    for (int i = 0; i < n; i++){
        fraction need;
        for (int j = 0; j < l; j++) {
            nums[i][j] = read();
            need += fraction(nums[i][j], 1);
        }
        need /= fraction(n, 1);
        fraction curr, prevleft;
        int idx = 0;
        for (int j = 1; j < n; j++){
            while (need > curr){
                fraction willtake = (one - prevleft) * fraction(nums[i][idx], 1);
                if (curr + willtake <= need){
                    curr += willtake;
                    idx++;
                    prevleft = zero;
                } else {
                    prevleft = (need - curr) / fraction(nums[i][idx], 1);
                    curr = need;
                    break;
                }
            }
            cuts[i][j] = fraction(idx, 1) + prevleft;
            curr = fraction(0, 1);
        }
    }
    for (int i = 1; i < n; i++){ // cut i
        pair<fraction, int> giveCut = {fraction(1e9, 1), -1};
        for (int j = 0; j < n; j++){ // person j
            if (!ordered[j]) {
                pair<fraction, int> other = {cuts[j][i], j};
                giveCut = min(giveCut, other);
            }
        }
        ordered[giveCut.second] = true;
        confirmed.push_back(giveCut.first);
        order.push_back(giveCut.second);
    }
    for (int i = 0; i < n; i++){
        if (!ordered[i]) order.push_back(i);
    }
    for (fraction i : confirmed){
        cout << i.num << ' ' << i.den << '\n';
    }
    for (auto i : order) cout << i + 1 << ' ';
    cout << '\n';
}

Compilation message

naan.cpp: In member function 'fraction fraction::operator-()':
naan.cpp:20:25: warning: narrowing conversion of '-((fraction*)this)->fraction::num' from '__int128' to 'long long int' [-Wnarrowing]
   20 |         return fraction{-num, den};
      |                         ^~~~
naan.cpp:20:31: warning: narrowing conversion of '((fraction*)this)->fraction::den' from '__int128' to 'long long int' [-Wnarrowing]
   20 |         return fraction{-num, den};
      |                               ^~~
naan.cpp: At global scope:
naan.cpp:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main(){
      |      ^
naan.cpp: In function 'int main()':
naan.cpp:120:14: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__int128')
  120 |         cout << i.num << ' ' << i.den << '\n';
      |         ~~~~ ^~ ~~~~~
      |         |         |
      |         |         __int128
      |         std::ostream {aka std::basic_ostream<char>}
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/9/ostream:166:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  166 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:170:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  170 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/9/ostream:702,
                 from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/9/bits/ostream.tcc:91:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   91 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/9/ostream:181:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  181 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/9/ostream:702,
                 from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/9/bits/ostream.tcc:105:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  105 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from naan.cpp:1:
/usr/include/c++/9/ostream:192:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  192 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:201:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  201 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:205:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  205 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:220:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  220 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:224:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  224 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:232:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  232 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:511:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]'
  511 |     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:517:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]'
  517 |     operator<<(basic_ostream<char, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:523:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]'
  523 |     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:528:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]'
  528 |     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
      |     ^~~~~~~~